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を解いていたのだが、このときは彩色数とはあまり考えなかったからねぇ。