2完1ペナ遅解き。俺に相応しいゴミのような成績だ。いや青パフォがゴミなわけはないんだけど、こういうコンテストだとそう思えてしまう。
A - i i's
難しい。だから400なのか。Nが小さいほど条件がきつくてコーナーケースが生じている可能性もあるので、とりあえずN=3を手で探す。見つかるが、長さ6で3が3個あるので3を1つおきに配置する必要があると気づく。じゃあN=9とかでも9をバラバラに置いてみる？うまくいかないが、しばらくいじっているうちに、9 8 9 8 9 8 9 みたいのを思いつく。これには7を隣接させることができる。8と9の間に7を置くことができる。これで解けた気がする。Nの偶奇で挙動が変わるか心配だが、実験すると大丈夫そう。端同士が同じ数じゃいけないの忘れてたけど、9 8 9 7 6 7 のように1個だけ入れ子にしないでおけば大丈夫。実装上は、9 8 9 を置いて 7 5 3 1 を置いてあとは小さい順に繰り返しを。
B - Red and Blue Spanning Tree
とっかかりがない。理解が深まるほど、解ける見た目をしていない。やることがないので、とにかく手を動かし続けるしかない。どうせ最小全域木のアルゴリズムに似た処理だろとも思ったが、しっくりくるものがない。「Yesだけど見つけるのが厄介」みたいのがなかなか見つからないので、何か解法はあるのだろうなという感触に変わっていく。具体的にはわからない。パリティとかも考えたけど、二部グラフを描いてみても何もない。完成品の辺の立場で、いくつの頂点が条件を満たすことに貢献しているかを考えると、1個の辺で最大2、辺はN-1個だから2*N-2、必要な貢献はN。引き算するとN-2。これはつまり辺の数よりも捨てていいものの数が1個少ない。少なくとも1個は、両端の頂点に貢献する辺がある必要がある。初めて手応えを感じた。そこから貢献数1の辺を伸ばしていくのを書いて提出してWA。
これが通らないなら用意できる解法はない。証明してないので仕方ない。コードを見直したり、要らないと気づいたUnionFindを削除してコーディング中に何かを見つけることに期待したり。自分の解法の反例を探していると、貢献0の辺があるケースも普通にあった。打開。改めて考える。貢献2の辺をあるだけ見つけて、そこから貢献1の辺を生やして残りを貢献0の辺でつないだとして、そのやり方で正解が発見できないことがあるか？パスで考えると貢献0の辺の隣の辺は貢献1が必要で、これは貢献1の辺を生やしていくことで到達できる（パスじゃなく枝分かれするものは考えてなかった）。さっき削除したUnionFindをまた入れる（裏目に出るのわりと珍しい）。難しい処理には見えないが、実装にかなり時間がかかった。今度はどうにかAC。
時間がかかった（2時間）けど、これは仕方ない。本当に難しいのだ。テキトーなコストを設定して最小全域木を作り祈るというのもあったけど、それよりは「Rの辺の両端にRの頂点」のような辺が一つは必要ということに早く気づきたかった。
C - Erase and Divide Game
異常に疲れている。CDの問題文を読んでいて読めなくて気づいた。なんとか両方読んだ。可能性を感じるのはCのほう。2で割っていったときの挙動を考えると、まあ2進法で考えればよかった（なんか気づかない）。制約は10^18と大きいが、これが10^5とかならトライ木で解けそうだ。数を60桁の2進法で表しリバースしてトライ木に入れて葉側から勝敗を決めていく。あとはこれをまとめて扱えれば。
