Refact.ai Match 1 (Codeforces Round 985)

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

D まずできるだけ辺を消す。次数2以上の頂点があれば、それを構成する三角形を消し、辺を減らす。すると森になるのでつないでいく。
次数2以上の頂点xに一回辺を減らす操作をしたら、そこはもう操作しなくていいと勘違いしてはまった。ランダムテストでなんとか気付けて良かった。

— titia (@titia_til) November 9, 2024

F. Palindrome Everywhere

　parityが関係するというツイートをヒントにAC。

・RRとBBが同時にあるとダメ

・Rが一個以下、または、Bが一個以下ならOK

　はコンテスト中に分かっていたが、

・RBBRBBはなぜダメなのか？

・RBBBRBBBRBBは良いのか？

・RBRBBRBBは良いのか？

　などは分かっていなかった。

・RBBRBBがダメなのは、相対位置の偶奇を考えれば分かる。（RBRBや、RBRBBBも同様）

R(x)BBR(y)BBのxからyを考える（x,yから同じ文字の方向を挟む方へ動かせる、と考える）と、xがRをまたぐときyもRをまたぐためxからyへたどりつけない。

・RBRBBRBBは良い。偶奇（Rの間に入っているBの個数）両方含まれるなら偶奇をずらせるので良さそう。

　ただ、さらに、

・「RBBRBB」（Rの間に偶数のものが二つある）が含まれていたら即ダメ、にも気付かなくてはいけない。

R(x)BBRB(y)Bのxからyを考えると、xの左右どちらかがRのとき、yの左右は両方Bなのでダメだった。

　これらが分からなくてはいけなかった。

　WAが出たテストケースから、何文字のとき間違っているか？　などを推測しながらやらないと解けなかった。時間があったら解けたかもしれないけど、コンテスト中だったら、ランダムテストを書いて考えなければ解けなかっただろうから、短い時間で解くのは結構厳しいね。