yukicoder contest 344

　最後二問残しの13完。

コンテストへのリンク

コンテスト後のツイート

J グラフを作って、遠いところへ飛んだボールから、そこへ届く人を探す。
K 差分を管理してシミュレーション。どこを消したかはBITで管理。
L 桁が一つずつずれていくので、途中の桁は一気に計算。
M あるxでの個数score(x)が分かれば二分探索。score(x)は再帰で実装できた。

— titia (@titia_til) May 20, 2022

No.1954 CHECKER×CHECKER(2)

　解説は見たけど、（パッと読んだだけではよく分からなかったので）大体自力でAC。

・まず、市松模様の片方のマス達を反転させる。

・S[i][j]とS[i+1][j]が異なる色なら、iまでの範囲を反転させる操作が必須。（jについても同様）

・S[i][j]とS[i+1][j]が異なる色なら、全てのjについてS[i][j]とS[i+1][j]は異なっていなくてはダメ。（jについても同様）

　を実装したらACでした。

　これで必要十分なのかはあまり分からずに書いたけれど、これで大丈夫そうですね。

　解けても良かった問題ではあるのだけど、もっと「これ」というような典型手法を使うんじゃないかと思ってしまい、こういう方向性では考えていなかった。

No.1955 Not Prime

　解説で2-SATだということを知ってAC。

　2-SATを使うのが久しぶりで、内容を忘れていた。

　論理式をCNFに変形し、$(a\vee b)=(\neg a \rightarrow b)\wedge (\neg b \rightarrow a)$と変形する。$\neg a $から$b$への辺と、$\neg b$から$a$の辺を貼り、SCCを作って、$x$と$\neg x$が同じ強連結成分に含まれないか調べる、という流れ。

　今回は、「Sに含まれる」を$x$とすると、「Tに含まれる」が$\neg x$となることに注意して論理式を書けばOK。

　2-SATだと分かった後も苦戦してしまったのは反省。