3完。制約に10^5がなかった。現在のレーティングは1935。1950を割ってるとコンテストが待ち遠しくなるね。
A - Ekiden Race
順位が下がったら可能性はないと気づく。もうちょっと解像度を上げると、誰かに抜かれたから可能性がなくなる。抜かれてなければタイムをいいように設定してできそう。結局証明できずに提出。
図にしづらいんだよね。
B - Insertion Sort 2
jだけ0-indexedなのがややこしい。「抜き出して」がわかりにくい。
端から合わせることができそうで、異常に簡単に見えるが、実装はきつい。
選んだ2個（P_iとP_(i+1)）を一つ隣にずらす操作を考える（全ての操作はこの繰り返しでできる）。すると、操作によって転倒数の偶奇は変化しないことがわかる。1から順に目的地へ移動させていく。合わせてない数が3個以上残っているとき、合わせたい数が右端にあるなら1回の操作で右端じゃなくできる。右端でないなら1回の操作で目的地へ運べる。1つの数を合わせるのに高々2回の操作で済むのでN*2回に収まる。最後の2個は合わせることができないが、ここが合っていないなら転倒数の偶奇が違うので不可能とわかる。合っているならそれまでの操作を出力すればいい。
実際に操作する部分の実装がきつかった。
C - Mex Game on Tree
数を書き込んだとき、影響が及ぶ範囲は自分と祖先のみ。自由度が高すぎて困っていたが、BobはKを書き込んでしまえばいいと気づいて少しずつ進んだ。Aliceの立場だと1手で（あるいは0手で）Kの部分木を完成させればOK。そうじゃなかったら？完成に2手かかるなら、Bobは邪魔ができそうだ。Aliceの行動はBobに潰されているので状況が好転しない。実装はbitsetを使った。
2WA。1回ならまあそういうこともあるけど、2回はいけないね。似た変数名を使っていたから起きたミスと、1個足りないとき-1のマスが必要なのを見逃したのと。
しかしこれけっこう面白かったけど、上位者にはギャグと言われてしまうんだな。
