ABC209 E - Shiritori (500)
コンテスト中の考察
全ての入力文字を6文字に正規化する
6文字未満なら一部を繰り返して6文字に増やす
6文字以上なら最初と最後の3文字ずつだけを残す
同じ文字列間のループは複雑になりそうなので代表の一つだけを使うことにする
対応する文字列の間に辺を張る
各点からDFSで勝敗を定めていく
既に決定している点だったらその結果を返す
既に探索中に訪れた点に来たら一時的に引き分けと判定する
勝ちになる点が有る場合、それを選ばれて負けるので負け
引き分けの点が有る場合、それを選ばれると勝敗がつかないので引き分け
それ以外の場合は勝ち
勝敗判定が間違っていた
ループ中の仮でつけた勝敗が実際には間違っている場合に正しい答えを出さないので駄目
解説の方法
文字列を点と点の間の辺として表す
点は三文字の文字列$ 52^3通り
トポロジカルソートの要領で勝敗を定めていく
遷移先が無い点から見ていく
辺を逆に見ていったときまだ結果が未確定の場合は以下のとおりにする
残りの出力辺のカウントを1減らす
今見ている点が負けなら辺の元は勝ちとしてキューに追加する
この辺を選べば相手を負けにできるため
残りの出力辺が0個なら辺の元は負けとしてキューに追加する
最後まで見て負けの点へ遷移が無いと言うことは全ての点が勝ちの点であるため
ループしている点は場合によっては見ないまま終わるがそれはループによって引き分けになっていると言うこと
それぞれの文字列で以下を出力する
選んだ文字列によって移動した先が
引き分けなら引き分け
勝ちなら後手
負けなら先手
最初の移動は選んだ文字列によって決まるため勝敗が後手視点になっている
辺の数は文字列の数になる