競プロチャレンジ供養会場: AtCoder Beginner Contest 209 E - Shiritori

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 2153 (記事作成時点)

供養

解法

• 任意のアルファベット3文字の文字列に対応する頂点からなる頂点集合 $V$ および、各 $s_{i}$ の先頭3文字に対応する点 $u_{i}$ から末尾3文字に対応する点 $v_{i}$ への辺 $u_{i} \to v_{i}$ からなる辺集合 $E$ からなるグラフを考える
• $s_{i}$ でしりとり開始のとき、$v_{i}$ から交互に辺を辿っていき移動できなくなったほうが負けとなる
• 先手番が到達したときに先手番の勝利が確定する頂点集合を $W$、先手番の敗北が確定する頂点集合を $L$ とすると、以下のようにして $W, L$ を決めることができる
  • 頂点 $u$ を始点とするある辺 $uv$ について $v \in W$ であれば $u \in L$
  • 頂点 $u$ を始点とするすべての辺 $uv$ について $v \in L$ であれば $u \in W$
• 各 $v_{i}$ について、$v_{i}$ から出ていく辺がないものについて $v_{i} \in W$ とし、上記の方法で $W, L$ を順次拡張しながら決めていく
  • 新しく追加された頂点 $v$ を終点とする各辺 $uv$ について $u$ を評価していけば拡張は最大で辺の数だけ行われる
• 各 $v_{i}$ について、$v_{i} \in W$ ならば Takahashi、$v_{i} \in L$ ならば Aoki、どちらでもなければ Draw を出力する

実装

計算量は $O(N)$

公式解説

躓いた点

• プレイヤーの挙動に関する記述が曖昧で出題意図を正しく汲み取れなかった