ツバサの備忘録

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

ARC087 E - Prefix-free Game

問題
提出コード

解法

グランディ数の問題かつ、二分木が関係していて…と割と惜しいとこまではいけた(つもり)なのですが、最後がうまくまとまらなかったので解説を見てACしました。
完全二分木を組み立て、そこに今回の文字列をうまく落とし込むと、現在選べる部分は小さい完全二分木であることがわかります。
1つ新たに文字列を追加すると、追加した場所によって、新しく選ぶことができる小さな二分木がいくつかできあがります。
ということで、この二分木をうまく利用してグランディ数を求めると、解説PDFにもあるように、現在求めたい二分木の高さをiとしたとき、そのグランディ数g_i
g_i= (i を割り切る最大の 2 の冪)
となります。あとは、初期状態で選べる二分木の高さをすべて求めることができれば、そのxorをとっていくことで勝者がわかるのですが、これはTrie木を利用することでうまく処理することができます。
自分はこちらの記事を参考にしました。
Trie木を作成した後は、再帰的にその木をたどっていくことで、選べる二分木の在処と、その高さを求めます。
そして、グランディ数を計算し、xorをとっていくことで、最終的な値が0であればBob、そうでなければAliceを出力して完了となります。