AtCoder Grand Contest 054

 　Cまでの三完で101位でした。Highest更新できて嬉しい！

　ただ、難問が解けたわけではないんですよね。早解き回では時々良い成績が取れるんですが、早解きが得意というわけでもないので、なんというか、運任せのようになってしまう。今回は、BもCも結構最初から正しい解法を考えていたけれど、偶然に近いものね……。

　もっと難しい問題を解く力を付けないと。

コンテストへのリンク

コンテスト後のツイート

B - Greedy Division

　初手で実験を書いたのが結果的には正解だったと思う。

　実験というのは、Wの配列に対して、どんな順列がありうるか……というのを順列全探索で求めるコードです。

　それを眺めていたら、「あれ、和がSUM/2に一致していれば、高橋君や青木君の取り方をどんな順番にしても、正しい順列が一つ求まるのでは？」と気付き（気付けば証明もしやすかった）、後はナップザック問題みたいな感じでした。

　計算量が四乗になるのがちょっと不安だったけれど、定数倍が小さそうなので大丈夫だろう、と提出したら無事AC。

C - Roughly Sorted

　これは、「2 1 4 3 6 5」でK=1の場合などを考えました。この例で、1や3はいくらでも後ろに動かせるけど、2が4の後ろにいくと途端にダメになるんですね。

　それを見て、「自分より前に登場している自分より大きい数の個数」がKに一致しているものしか動かせないんだな、と気付けました。

（DかEはできれば解説ACしたい）

Codeforces Round #728 (Div. 1)

　A一完のひどい出来。

コンテストへのリンク

コンテスト後のツイート

B. Tree Array

　制約から、三乗の解法を考える。

　全てのi, j (i < j)について、j が iより先に使われる確率を考えれば良い。（主客転倒って言うのかな？）

　そうすると、iとjを結ぶpathにいくつか余計なものがくっついているような図を考えることになる。（木の直径を図示するときのやり方と同じ）

　なので、iとj上のpath上の点から始まったとき、jの方に先にたどりつく確率を調べればOK。

　……と、ここまではできたが、この確率が2ベキの和になると早合点してしまった。それでサンプルが合ったこともあり、修正できず終了。

　実際は、iから距離p、jから距離qの点からスタートしたなら、p回iの方へ進む前に、q回jの方へ進む確率を計算すれば良いので、p*qのマスで端から端への最短で向かう経路数を考えるのと似たようになる。これはDPで求めることができる。

　これを前計算すればOK。

　多分、もう少し時間が残っていて、落ち着いて考えていたらちゃんとACできたと思う。先にCを考えたりしたせいもあり、Bの正しい方針に至ったときに時間が残っていなかったのが敗因か。

　

AtCoder Beginner Contest 206（Sponsored by Panasonic）

 　Eまで五完でした。

コンテストへのリンク

コンテスト後のツイート

F - Interval Game 2

　すぬけさんの解説を聞いてAC。

　NIMみたいなことをするのでは？　Grundy数を使うのでは？　とは多少は考えたものの生かすことができなかった。

　ある一つを選択したら、左右に残った二つの区間のGrundy数のxorがそのGrundy数になる、というのはちょっと思ったのだけど……。

　それに加えて、どういう遷移があるかを考えなくてはいけなかった。

　Grundy数を考えたいのだからどのような遷移があるかを考えるのは当たり前で、「いくつかの区間が選択可能」なときのGrundy数は、それぞれを選択したときのGrundy数のmexとなる。

　Grundy数の定義通りなのだけど、遷移を意識していないと書きにくい気がする。Grundy数と区間DPって相性が良いんだね。

Codeforces Round #726 (Div. 2)

 　Cの誤読でハマったものの、なんとか全完。Div. 2のCくらいだと、この後に解ける問題があるはず！　と、ちょっとハマったら飛ばす決断ができるんだよね。これが、ARCとかこどふぉDiv. 1だとなかなかそういう決断はできない。

コンテストへのリンク

コンテスト後のツイート

　ツイートに付け加えることは特になさそう。

　Dの正当性は、Kiriさんのツイートで理解しました。なるほどー。

AtCoder Beginner Contest 205

　Eが解けずに終了。ただ、Eは知識問題に近かったので、まあ仕方ないか。次に類題を見たときは解けるようにしたい。

コンテストへのリンク

コンテスト後のツイート

E - White and Black Balls

　解説AC。

　経路数の問題なのは分かるが、それをどうやって求めればいいか、というところで詰まった。解説の図を見てなるほど、となった。

　この求め方は見たことがあったと思うが、身に着けておかなくてはいかない知識とは思っていなかった気がする。

　次出題されたときは解きたい。

Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)

　Cまで三完。D、Eを考えていたが解けずに終了。ここまではっきり失敗したのは久しぶりな気がする。

コンテストへのリンク

コンテスト後のツイート

D. Lost Tree

　「木は二部グラフ」というキーワードすらほとんど浮かんでいない。

　クエリの回数がn/2というところから、二部グラフは考えるべきなんですよね……。

　そのキーワードを思い付くことが重要で、その後は、一回目のクエリで二部グラフのどちらに属しているか判断できる、と気付くところがポイントですね。

　二部グラフを使おうと思いついていたとして、そこで詰まっていた可能性はありそう。

E. Lost Array

　全ての要素についてクエリで聞いた回数が奇数回になれば良い、というのは分かった。では、それが実現できる最小の回数は？　というところで詰まった。

　なんか条件（1の個数や3の個数を調べて……みたいな）がないかと考えていたけど、上手くいかず終了。

　実際は、もっと愚直に構成できるか試してみるべきだった。

　ただ、毎回それをやっていると、$k=n-1$のときにTLEしてしまう。このときは、n回聞けば良いと分かるので、場合分けしてやればACできた。

　公式解説は（理解できていないが）もっと賢い方法でやっているようだけど、上記の方法はコンテスト中に考えたことをまとめただけなので、コンテスト中に通すことは可能だったはず。

　計算量を気にする前に、愚直なやり方で間に合わないかを試してみるべきだった。

第二回日本最強プログラマー学生選手権

　ABCDFで終了。Eはコンテスト後、自力で解けたもののかなり苦戦した。

コンテストへのリンク

コンテスト後のツイート

G - Spanning Tree

　行列木定理を知らないとどうしようもない。

　これを知れたのは良かった。（証明は理解できてないけど）

　行列式の計算もはじめて書いたと思う。なるほど、掃き出し法を使うことで三乗に収めるんですね。

　ケイリーの公式といい、この行列木定理といい、知らないと思いつくのが難しい（が、競技プログラミングに出題される）定理が木の分野にはありますね。

H - Shipping

　最近、SRMで類題を見たので、解説ACしました。

　公式解説の「ハッシュを使った解法」は凄いですね。サイクルの部分はSRMのものと同じですが、木の部分もこうやって処理できるとは。

　SRMのときはサイクルのところしか読まなかったので、木の部分はどうするんだろう、と考えていたのですが、LCAを使うしかないのかな……と思っていたところでした。しかしこれもLCAを使わずにハッシュで解けるんですね。

　とはいえ、このハッシュの使い方はこのFと同じか。

　いくつかの状態があって、そのうちの一つでも存在するかどうか調べたい……というときはこのハッシュ（Zobrist Hash）を検討しても良いのかもしれない。