tokuminiさんのAtCoder Regular Contest 156での成績：487位
パフォーマンス：1856相当
レーティング：1810→1815 (+5) :)
https://atcoder.jp/users/tokumini/history/share/arc156?lang=ja
A、B問題を40分・1WAで解いて平々凡々な成績。
今回も順位表は見ないと決めていて、残り時間はC問題とD問題をそれぞれ30分ずつほど手を付けて、C問題の方がまだ可能性ありそうかと考えて何度か適当な考察で提出していた。
A - Non-Adjacent Flip
とにかく場合分けをしていろいろ考えていく。
- まず1が奇数個ならできない
- 1が4個あれば最短手数で消せる
- 1が2個で連続していると、いろいろ起こる
- 11 : 無理
- 011 : 無理
- 0110 : 3回
- 0011 : 2回
など。丁寧に考えるとできるのだけど、焦っていたので1WA。
B - Mex on Blackboard
パッと見簡単そうなのに考えていくと「あれっ、違うな」と何度もなる問題だった。
結局、新規追加する数字として最大のものを全探索し、そこまでは最短手数でいき、それ以降は最大までから選ぶ、と考えることでなんとかなった。
紙で考えていた量が少なく、コード書きながら合わせようとしたのが良くなかったかもしれない。この塩梅は常に難しく、常に迷いどころ。
C - Tree and LCS
各ノードから部分木について、
- 一番長いパスだけは上に伝達
- それ以外はここまででreverseする
という謎のアルゴリズムでサンプルは合ってしまったので何回かその亜種などで提出してみたが全然ダメだった。
解説の方法でできることは理解できるが、他の方法でダメなことや解説の方法を思いつく手段が難しい。
D - Xor Sum 5
XORをごちゃごちゃするのは競プロ的によくある話なので、もしかしたらこっちの問題のほうがCよりも解ける可能性あるかもしれないとは思ったが、やってみるととても難しい。解説を見ても難しい。
所感
全体的に、このコンテストから何を学ぶかというのが掴みづらい感じはする。解けるものは解けて、解けないものは解けないという二分化状態から脱する鍵がどこかにあるのかどうか。
