ABC209 E Shiritori
しりとりを扱う問題の典型的な考え方として, 頂点を文字(接頭辞・接尾辞), 辺を単語(接頭辞から接尾辞へ)としたグラフに帰着するというものがあり, 今回も先頭3文字, 末尾3文字についてのグラフを考えてみる. ここで, 解法の候補として, メモ化再帰が思いつくが, そもそも再帰をすることが困難であり, 工夫しても通ることはない. また, 状態数を増やして前からDPしようとしても制約が大きいため厳しい.
負け状態: 次の手が存在しない場合, あるいは勝ち状態にしか遷移できない場合
勝ち状態: 負け状態に遷移できる場合
引き分け状態: 勝ち状態でも負け状態にも遷移できない場合
このようにして解法自体は完成したので, 実装を考えてみよう. ここで, 1個状態が確定すれば, その影響を受けるのは隣接する状態のみであるという性質を利用する. 逆辺(接尾辞 → 接頭辞)を張ったグラフにおいて, BFSをしていくことを考える. すると, 次のように遷移できることがわかる.
今の状態が負け状態であるとき
逆辺をたどった後の頂点の状態は勝ち状態となる.
今の状態が勝ち状態であるとき
逆辺をたどった後の頂点について, その隣接する頂点がすべて勝ち状態である場合, その頂点は負け状態となる. これは, 各頂点について出次数をもっておき, 逆辺をたどるごとに到着した頂点の出次数を1ずつ減らし, 負け状態から遷移することなく出次数が0になったときに負け状態とする というように実装できる.
このようにして, この問題を$ O(N \log N)で解くことができた.