完全に解けていたはずだったのですが、ライブラリがバグっていることに気づかずヒドイことに…

解法

結論から言えば、接尾辞木の上でよくあるゲームをしていると考えると解ける。
結局の所、問題文のゲームが何をしているかというと、

というものになる。
当然ながら、辿ってきた順にノードが示す文字を連結すれば $S$ の部分文字列になるので、元のゲームと同じ結果が得られる。

あとはよくあるゲームの解法で、葉では必ず偽（つまり負け）を返し、中間ノードではすべての子が真を返すなら偽（つまりどの子に進んでも相手が勝つので自分が負ける）、そうでないなら真を返すようなDFSをすれば、どちらが勝つかわかる。

接尾辞木の構築方法は色々あると思うが、私はそういうライブラリを持っていなかったので、SA-ISで接尾辞配列を構築し、接尾辞配列の上で二分探索をして代用した。

提出コード例は以下の通り。

あとがき

我ながらキレイに解いたな〜などと悠々コードを書いて提出したら謎のREがでて、本当に焦りました。
どう考えても間違っていないはずなのに全然合わず、EFが解けなくて時間がなかったのでランダムテストを書く暇もなく、混乱しているだけでコンテストが終わってしまい反省です。

結果的にはSA-ISのライブラリがバグっており、ac-library-rsなら通りました。久々にこの手の絶望を味わいました。
コンテスト後にめっちゃランダムテストをかけてもなかなかキラーケースに出会えなくて難儀でした。

ともあれ、ライブラリのテストも強化できましたし、たぶんもうバグってないはずです。（フラグ）