ARC087-E Prefix-free Game

問題リンク

解法

とりあえず問題概要を読むと、完全二分木を書くとよさそうなので書いて考察してみる。

頂点を文字列に対応づけると、根から $x$ までのパスに $y$ が含まれるか、$y$ までのパスに $x$ が含まれるようなすべての $y$ は、$x$ で表される文字列が入っている時に入れられないことがわかる。 要するに、根から $x$ までのパスと $x$ の子孫が全滅する。

こうしてすでに入っている文字列をつぶした木を考えると、これはさまざまな大きさの完全二分木の集合体になる。 これをどんどん削っていって操作ができなくなった方が負けなので、Grundy 数を考えてやる。 実験すると、$K$ 段の完全二分木の Grundy 数は $K$ の最下位ビットに等しいので、これを計算できればいい。

実装では、Trie を使えば視覚的にもわかりやすく実装できるが、面倒だったのでローリングハッシュで判定した。

提出リンク

感想

非 Nim の Grundy 数の問題を自力 AC したのが初めてなので、勉強になった。 あと、ライブラリのローリングハッシュがバグりまくっていて大変だった。