AtCoder Regular Contest 195 (Div. 2)

　三完はしたがレートは落ちた。Bは同じ解法で通している人を何人か見かけた。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 195 (Div. 2) Cまで通したけど、Bは嘘解法だと思う……
A 前からと後ろから
B k=A_1+B_1を固定すれば判定可能。kの絞り方が分からない。結局、a in A,b in Bについてa+bを列挙し個数を見て、その個数がOKになりうるもののみ判定した。
C Rが奇数ならダメ。あとは地道にやる。

— titia (@titia_til) March 23, 2025

B - Uniform Sum

　嘘だと思ったが、（嘘かもしれないけど）それほど嘘ではなかった。

　A, Bがdistinctだとすると、S=A[i]+B[j]が何個ずつ現れるかをカウントすれば、それを見るだけで判定できる。

　今回はdistinctじゃないのでもう一工夫必要だが、大体それで良かった。

　distinctなら上手くできるのでは？　と考えるべきでした。

D - Swap and Erase

　解説AC。

　コンテスト中に考えていた貪欲（左から見ていき、A[0]==A[2]ならA[1]とA[2]をswapする）がどういうときまずいのか気付けなかったのが敗因。

　たとえば、

・1 2 1 1 1

　のときまずかった。A[0]とA[1]をswapしなくてはいけないときもある。

　Aの各要素が高々一回しかswapされないというのは言われてみれば自然だし、貪欲でダメと分かればDPしようと思えた可能性はあるかもしれない。

E - Random Tree Distance

　解説AC。解説放送も見た。

　まず、lcaを考える（u,vの距離を、D[u]+D[v]-2*D[lca]とする。D[x]は1からxまでの距離です）のはすべきだった。lcaがどこにあるか分からないから、lcaを考えることで状況が良くなるとすぐには思えないけれど、これはまずして良いですね。

　あとは、D[lca(u,v)]が、u<vのときvの値によらないと気付けるか、だが、これは実験していれば気付けるかもしれない。しかし、その後、D[lca]に関する漸化式を立てる部分が理解できず、解説を見ながら悩んでしまった。lcaが再帰的に決まっていく、と考えれば難しい式ではないのだが……。

　発想があった方が良い部分（D[lca(u,v)]が、u<vのときvの値によらないと気付く部分）もあるけれど、それ以外の定石的な部分でも詰まっているので、その部分はどうにかしたい。