JOI 2011 代表選抜 Day1, Day2 解答解説
今年は時間の関係で解説がまだないので、非公式な解説を載せます。Dragon以外は満点コードはわかっていますが、この解法が想定解である保証はありません。解答コードは前の記事参照。
Day1についてはqnighyさんが分かりやすい解説をして下さったので適当にします。多分Day2のほうが需要あるのでDay2はわりとまじめに書きます
Day1 Banner
マス目があり、それぞれ3色のうちどれかに色がついている。マス目を頂点とする長方形で、四隅あわせると3色に塗られている長方形の数を求めよ。
X方向に2つ長方形の軸を決めて、Y方向に各組み合わせのやつを数える。O(W^2H)ぐらい。
Day1 Dragon
ドラゴンがIOIの妨害をする。マス目があり、ドラゴンがいる。マス目には1人までしか選手が入れない。ドラゴンと同じ行、列のマスではドラゴンのせいで選手が入れない。しかし、理事長が防火装置をもってどこかに立つ。理事長がドラゴンとの間にいると、ドラゴンに攻撃されない。最大何人の選手がマス目に入れるか。但し、理事長と同じマスに選手は入れない。
ひたすら実装する
Day1 Joitter
JoitterというSNSでは、日記の公開規則を(1)友人(2)友人ないし友人の友人(3)友人関係をたどってたどりつける人 のいずれかから選ぶ。友人リストに追加するにはコストがかかる。全員が互いの日記を見れるようにするのに、何回のリスト追加が必要か。また、そのときコストはいくらか。
場合分け。(1)がいたら(1)の人を他の人とつないで終了。(1)がいなくて(2)が3人以上いたら、星型グラフ(ある頂点が存在して、その頂点と他の頂点はすべて結ばれているようなグラフ)をすべて試す。(2)が2人だけいたら、星型グラフもしくは、その2人同士と、他の全員がその2人のうちどちらかに結ばれているようなグラフになる。(1)(2)どちらもいなかったら、最小全域木。
Day2 Guess Them All
1〜Nの置換である数列が正解として決まっている。あなたは高々L回、次のことを行える。「1〜Nからなる数列を与えて、何個の数が正解と一致しているかを得る。全部一致していたら終了」L回以内で正解を求めよ。
N=1の場合は自明なのでN>=2の場合で考える。
「N個の要素のうち、ある1個だけが2で、他が1である」数列を考える。答えが1のときはよくわからないが、2のときは「2」が正解の位置に来たことが分かる。0のときは「2」が正解において「1」の位置に来たことがわかる。これにより、高々N回の試行で1の位置を決定できる。
1の位置を決定したので、1をダミーとして使える。2以上の数の位置を決定する。これは、二分探索を使って、「2222…2211…11」のような数列を使うと、log N回ぐらいで決定できる。今1の位置はわかっているので、純粋に調べたい数の位置についての情報が得られる。
しかし、このままだとN<=100, L=700のケースで800回ぐらいの試行が行われてよろしくない。ここで、すでに数が決定している位置はもう考える必要がないので、log N + log (N-1) + … + log 1ぐらいで決定できることがわかる。これだと、N=100の場合も計算上670回弱で正解を得ることができる。これにより、満点が得られる。
Day2 Keycards
N (1 <= N <= 1,000,000) 箇所の穴の候補位置があるカードキーがあり、異なるカードキーは2N枚存在する。異なるカードキーが1枚以上渡された。全部重ねたらK箇所の穴がみえたという。そのような渡され方が何通り存在するかを、素数1,000,000,007で割った余りの数を求めよ。
まず、NCK通りの重ねたときの穴の位置が考えられる。「N-K箇所の穴の候補があり、重ねたら穴が見えなかった」という状態を想像すればよい。
ここでDPを使うと、sol[p][q]はq>=1のときはsol[p-q][0] * pCq として求められ、q=0のときはsol[p][0]+…+sol[p][p]が22p-1であることより、順次決定できる。しかしこれだとO(N^2)かかり、しかもこれ以上改善できそうにない。
とりあえず、N=Kの場合は明らかに答えが1なので除外する。
N>Kの場合は、次の式を使うと直接答えを求められる。証明は面倒なので略。
sol[p][0] = Σ(-1)i * pCi * 22p-i
ここで問題となるのは、pCiと22p-iを高速に求めることである。後者は、22i = (22i-1)2 より順次、高速に求められる。
前者は若干面倒であるが、予め1〜Nの階乗と、その逆元を計算しておくことで直ちに求めることができる。逆元はそれぞれO(log N)で計算できるので(ユークリッドの互除法もどき)、結果O(N log N)になる。りんごさんによると逆元を求めるところで「全部でO(N)」にできるらしく、それを行うとO(N)になるらしい。
Day2 Shiritori
100種類の文字がある。それらの文字で5文字の単語がN個(N <= 500,000)辞書順に与えられる。しりとりでつなげよ。たくさん答えがあるなら、辞書順最小のものを返せ。
かなり大変な問題である。
文字の種類数をKとおく。
まず、しりとりをするということを、「文字を頂点とし、単語は文字から文字への辺となるような有向グラフを考えて、ある頂点からある頂点まで、すべての辺を通って行く」というように解釈する。これができることと、「すべての頂点が辺で連結」かつ「ある頂点に対して、入ってくる辺と出る辺の数の差は高々1であり、差が1であるような頂点は高々2つしか存在しない」は同値である(証明は略、というか不明)。また、「出る辺の数が入ってくる辺の数より1多いような頂点」が存在する場合、常にそこからしりとりが始められる。そのような頂点が存在しない場合は、辞書順条件より、辞書順最小の単語を使うような頂点から始めればよい。ここで、しりとりの可能性が判定できる。
ここから、条件を満たすように辺を選んで進んでいく。「辺の出入りの差」条件は今いる頂点から出ている辺を選んでいる限り破られることはないので、連結条件だけ考えればいい。しかし、この連結条件を考えるのがわりと大変である。
まず、同じ頂点を結んでいる辺が複数出ている場合、その辺は（辺が複数存在する限りは）自由に使うことができる（その辺を選んでも連結条件は相変わらず成立するので）。
辺が1本しか出ていない場合は、「その辺をたどったとき、連結条件が満足されるか？」という確認をしなければならない。これは、素朴に実装すると「各辺に対してチェックする際に」O(K^2)の計算量がかかる。そのまま実装すると、N回辺をたどる必要があり、各回K本の行き先について調べていたら、最悪O(K^3N)とかいう大変な時間がかかってしまう。これだと到底N=500,000のケースには間に合わない。
ここで、「ある辺を選んでよいか悪いか」という情報は、辺が消えない限り変わらないことに注意する。すなわち、辺が消えるたびにすべての辺に対してその辺を選ぶことが可能かを確かめるという手法が利用できる。これを用いると、辺をたどる際には各行き先O(1)でチェックできるので辺をたどる分の計算量はO(KN)になるが、辺を選ぶことができるかのチェックに素朴な実装だと最悪O(K^6)かかってしまい、むしろひどくなってしまう。
しかし、この辺の通行可能性チェックは「各辺に対してO(K^2)」から、「すべての辺に対してO(K^2)」までオーダーを下げることができる。
これには、強連結成分を用いる。まず、今の辺の連結性をもとに強連結成分分解を行う。これはO(K^2)で実行可能である。
ここで、同じ強連結成分間を結ぶ辺は、通行可能であることがわかる。移動先から、その辺を使わずに同じ連結成分内の他の任意の点へ移動可能だからである。
また、「他から到達されない強連結成分」について、「成分に属する頂点数が1」でかつ、「そこから出る辺の数が1」であるときには、その辺を使うことができることもわかる。
さらに、上記の条件を満たさない辺は通行不可能であることもわかる。これにより、O(K^2)ですべての辺に対しての通行可能性チェックを行うことができた。
この手法を辺が消えるたびに適用すれば、O(K^4 + KN)で辞書順最小の解が得られ、これでようやく満点を得ることができる。
