NECプログラミングコンテスト2021(AtCoder Beginner Contest 229)

　Eまで五完でした。見直すと、FもGもシンプルで解けなくてはいけない問題だった。

コンテストへのリンク

コンテスト後のツイート

NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) Eまで五完。F分からなかったし、Gはあと少しだと思ったけど違ったっぽい。
D 尺取り
E 後ろからUnion-findで。

— titia (@titia_til) November 27, 2021

F - Make Bipartite

　解説AC。全く思いつかなかった。

　結構長い時間フローを疑っていたのが良くなかったか。実際にDPして色塗りしていこうとは思わなかった。

　一直線上だったらまずDPを疑ったと思うのだけど……。うーん、図形に引きずられたか。

・各頂点からの辺の数が少ない

・規則性があるので、1→2→3→……と順番に決められそう

　あたりを思えばDPは自然ですね。

G - Longest Y

　解説AC。

　D問題に引きずられたのか、尺取り法を使おうとして失敗。Yの位置だけを取り出し、累積和を使うと、（寄せるべき中央のindex, 左端のindex, 右端のindex）を決めたらO(1)でswapのコストが得られることまでは分かっていた。

　問題は、中央のindexが(左端+右端)/2として求められることに気付かなかったこと。それが分かれば答え決め打ち二分探索を使うのは自然だった。

　中央値というのはちょっと考えたはずなのだけど、最後実装しているときは忘れていたね……。尺取りで上手くいかない、と思ったときにもう一度解法を考え直さなくてはいけなかった。