AtCoder Regular Contest 141

 　ABの二完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 141 C～Eを読んで、一番いけそうに見えたCに行ったが解けぬまま終了。
A 「2個以上連結」を「2個連結」と勘違いして失敗。
B 最上位bitは増えるしかない。

— titia (@titia_til) May 29, 2022

C - Bracket and Permutation

　解説AC。

　公式解説の方法は全く考えなかった。

　辞書式順序の条件がなくても、PとQを満たすような括弧列というだけでそこそこ括弧列が絞れる。そのため、そこだけに注目してしまいがち（だし、実際そこから解いた人もいるようだが、その解法はよく分かっていない）だが、PやQが辞書式順序で最小・最大であることを利用しつつ絞ろうとすると解法の方法が思いつける（のかもしれない）。

D - Non-divisible Set

　解説放送を見てAC。

　各数を2ベキで割った余りで分類するのが重要で、その処理をした後は割合自然な考え方だと思った。

　が、実際は、分かった（つもりになった）後も実装で苦戦。全部が”No"（つまり、良い集合を一つも作れない）かどうかを判定するのが結構難しかった。

E - Sliding Edge on Torus

　解説放送を見てAC。

　Union-findを使うことはコンテスト中も思いついたが、同じグループ同士に辺が貼られた場合の処理が面倒くさそうで避けてしまった。

　だが実際は、重み付きUnion-findを知っていればたいして面倒ではなかった。

　振り返ると、C～Eの中では一番ACできた可能性があったか。

　長いことこのライブラリを使っていなかったので、本当に思いつけたか、という不安はあるが、この三問の中では一番自然な発想で解法に至れるし、ライブラリがあれば実装も大変でない問題だったと思う。