ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC048 D - An Ordinary Game

問題
提出コード
グランディ数を利用する問題は、ぱっとみで使うだろうなーというのがわかっても、そこから答えに結び付けるのが難しくていつも解くのに時間がかかります…

解法

お互いが操作できなくなる状態では、必ず2種類の文字になっていて、それが交互に並んでいるような状態になります。
ababa...のような状態です。
ababacacaca...やababcaca...のような状態でも、まだまだ文字を削除できます。
このことにさえ気づくことができれば、あとはいけると思います。
このようなパターンでありうるのが、
ababab...baという、両端がそろっている状態、もしくは
ababab...abという、そろっていない状態です。
そして、両端の文字を消去することができないという問題の条件から、どっちになるかは初めから決まっています。
前者のパターンでは、最終的に文字数が奇数に、後者では偶数になります。
また、最初の文字の偶奇は簡単に調べることができるので、お互いが最善を尽くしたときに消去できる文字数の偶奇がわかります。
この偶奇が、結局は勝者を決めることになります。
ということで、初期状態の文字数の偶奇と、両端が同じ文字であるかどうかを2進数で表し、2つの排他的論理和をとると、勝者がわかります。