AtCoder Regular Contest 171

　AB二完。まあまあ速かったのでレートが減ることはなかったが、難しい問題が解けないなぁ。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 171 Bまで。
A ルークをA個おいたとき、ポーンがおける個数はmin(N-A,(N+1)//2)*(N-A)
B index i<j<kが同じ数字かつP[k]=kなら、P[i]=P[j]=kとしなくてはダメ。あとは、操作で値が変わらないように決める。
C 木DPしようとしたが、遷移できず終了。考察が間違っていたっぽい。

— titia (@titia_til) February 4, 2024

C - Swap on Tree

　解説AC。

・どの辺について操作するかを決めたとき、「各頂点で、どの順番で辺を消していくかを決めるかと操作終了時のAが定まり、それらは全て異なる」

　ということに気付かなくてはいけなかった。

　コンテスト中は、ある頂点をどこへ移動させるか……というようなことを考えていて、順番が大切だということは分かっていた。そこから類推して、順番さえ決まれば数列が定まるのでは？　と思わなくてはいけなかった。

　その後の木DPも結構難しいが、ここまで分かっていれば遷移式は立てられるか。

D - Rolling Hash

　解説AC。

　コンテスト中は問題を読み、ニ十分くらい考えたが何も思いつかなかった。BがPの生成元になっているかで条件が変わってくる？　とか考えていた時点でダメ。まず、B=1のときに解けるかを考えるべきだった（今回は、それが答えになっている）。Bが本質的には関係なさそうなのはまあそうなので、B=1で考えるのは自然。

　B＝1のときはグラフの彩色数を求めれば良い、というのもしばらく納得できなかったのは、彩色数の定義が頭に入っていなかったせいか？

　グラフの彩色数自体はこのFを解いていたのだが、このときは彩色数とはあまり考えなかったからねぇ。

AtCoder Beginner Contest 187

 　年も変わったし、コンテストへの参加記録を書いていきます！

　……といっても、コンテスト後、既に一日経っている。いつまで続けられるんでしょうか。

コンテストへのリンク

コンテスト後のツイート

D - Choose Me

　何もしないと全員が青木氏に投票する。

　高橋氏が演説を行うと票がどれだけ動くか、と考えると、2*A+Bでソートすれば良いと分かる。

E - Through Path

　最初、全方位木DPが必要だと思い一旦飛ばした。

　Fを解いた後、やりたくないし書き終える自信がないけど、全方位木DPを書くかー、と書き始めたら、通常の木DPでいけることに気付いた。

　自然に書けば全方位木DP、「全体にxを足して、逆側からxずつ引く」ことを思いつけば普通の木DPでいける。

　とはいえ、全方位木DPでも書けるべき問題ですよね。

F - Close Group

　Nが小さいのでbit系を色々考えたが、しばらく思いつかず苦労した。

　「まず、完全グラフになっているものを列挙」を思いつけば、$4^N$のDPにはたどりつける。

　それが実は$3^N$になるというのは、この問題のsnukeさんの解説動画で覚えていた。難しい問題を解説ACしておいたのが役に立った！　と嬉しかったのですが、Educational DP Contestのこの問題もそうだったのですね。解いたはずなのに全く覚えていなかった……。