AtCoder Regular Contest 198 (Div. 2)

　Bまで二完。レートが落ちたが黄色には残った。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 198 (Div. 2) AB二完。
A 偶数
B 実験すると、(1,2,1)や(1,1,1)減らせる。減らしたときXがマイナスにならなければYes。ただし、Z=0でYが奇数のときはダメ。
C 左端から合わせる。最後の辻褄合わせは(0,+1,-1)や(0,-1,+1)を四手・六手で構築できて勝ったと思ったんだけど、WA。

— titia (@titia_til) May 25, 2025

C - Error Swap

　自力AC。惜しいようで惜しくなかった。

　大まかな考察は合っていたけど、詰めなくてはいけない箇所が残っていた。

　左端から揃えていく、という解法でやった。index iを揃えようとするとき、B[i]+1に一番近いA[k]を探して、A[k]が小さいなら左回り、大きいなら右回りに回転させて、B[i]+1になったらクエリ(i,j)を投げる、という方法でやっていた。

　だが、A[i]=B[i]+1となったときに(i,i)と投げられないのが問題だった。(i,N),(N-1,N)とすれば(i,N-1)とできるのだが。ここに気付いていなかった。

　ここを修正してAC。

　あと20分くらいは必要だったか。

D - Many Palindromes on Tree

　自力ACはしたが大変だった。

　問題の内容を理解するのがちょっと大変だが、理解できれば解法そのものは難しくない。(i, j)間の距離が大きいペアから、A[i][j]=1なら、一つ近づけて(i', j')も1にし、Union-findでくっつける、という操作をする。

　その上で、今度はその逆順で答えを構成していく。

　しかし、この順番を構成する部分（上の(i', j')に対して、(i, j)が何かを前計算したりする）の実装で苦戦。さらに、ちゃんと実装してもMLEになり、PyPyでは通せなかった。二次元配列にしていたり、tupleで実装しているのを整数化したりすれば解消されるのかもしれないが……。

　RUSTに直してもらいAC。今回は、Gemini Canvasを使ってみたら、一発だった。