Shiritori [AtCoder Beginner Contest 209 E]

https://atcoder.jp/contests/abc209/tasks/abc209_e

前提知識

• 後退解析（ゲーム問題）

解説

https://atcoder.jp/contests/abc209/submissions/24158002

ゲーム問題は手法が限られているので、なにも思いつかない場合はとりあえず全部の手法を1つずつ試していけばいい。
今回は後退解析で問題が解ける。

後退解析？

とある状態の勝敗をその状態からの遷移をすべて確認することで勝敗を決することにする。
遷移先がすべて勝ち状態であれば、どのような行動を選択してもその先の状態は相手の勝ち状態となるので、
どうあがいても勝てない。よって、その状態は負け状態となる。
逆に遷移先に1つでも負け状態があれば、その行動を取れば、相手に負け状態を押し付けることができる。
よって、その状態は勝ち状態となる。

よって、とある状態の勝敗を判定するには、そこから遷移する状態すべての勝敗が分かっている必要がある。
つまり、状態がより深い所、行動を行った末端の状態から勝敗が確定していき、逆向きに勝敗が確率していくことになる。
このような性質を考えて、遷移先の状態から勝敗を決して行く方法を後退解析と呼ぶ。

なお、この問題は後退解析の入門問題としては適さない。
もし知らない場合は入門的問題をまずは済ませることを勧める。

今回の問題では

後退解析では、すべての状態について考える必要がある。
今回はどのように状態化すればいいかを考えると、ユーザーがとある状態にいるときに考えるべきは、
しりとりで次の用語を決定するのに使う3文字である。
この状態以外に今後の意思決定に必要な要素はないので、3文字だけを状態として持てば十分。
この状態数を考えると、これは全列挙しても間に合う計算量である。

よって、しりとりの先頭3文字、末尾3文字を状態として取ると後退解析に持ち込めそうな感じはする。

ループ構造が出てくる可能性があるというのが大変な部分である。
よって状態を「勝ち」「負け」「ループ（＝引き分け）」の3種類で管理していくことにする。
勝ち・負けの条件は先ほど話した通りで、この条件によって状態が決していないものを勝敗を確定させることができない、
つまり、引き分けとして判断する。

実装について

queueを使って状態が確定したところから辺を逆にたどって確定する状態を探しながら実装していく。
一般的な後退解析の実装とそれほど変わりはない。
ループがあるので、一部確定しないまま処理が終了してしまうが、それは引き分け状態なので問題ない。

後は、文字列の扱いであるが、自分はmapで間に合うかなと思って実装したら間に合った。
実行時間も2sだったので、文字列を数値化して普通の配列を使う方がいいだろう。

int N;
string S[201010];
map<string, vector<string>> E, RE;
map<string, int> ans, cnt;
enum { LOOP = 0, LOSE, WIN };
string statements[3] = { "Draw", "Takahashi", "Aoki" };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];

    set<string> nodes;
    rep(i, 0, N) {
        string pre = S[i].substr(0, 3);
        string post = S[i].substr(S[i].length() - 3);
        E[pre].push_back(post);
        RE[post].push_back(pre);
        cnt[pre]++;
        nodes.insert(pre);
        nodes.insert(post);
    }

    queue<string> que;
    fore(cu, nodes) if (cnt[cu] == 0) {
        ans[cu] = LOSE;
        que.push(cu);
    }
    
    while (!que.empty()) {
        auto cu = que.front(); que.pop();

        fore(pa, RE[cu]) if (ans[pa] == LOOP) {
            cnt[pa]--;
            if (ans[cu] == LOSE) {
                ans[pa] = WIN;
                que.push(pa);
            }
            else if (cnt[pa] == 0) {
                ans[pa] = LOSE;
                que.push(pa);
            }
        }
    }

    rep(i, 0, N) {
        string post = S[i].substr(S[i].length() - 3);
        printf("%s\n", statements[ans[post]].c_str());
    }
}