実はこの問題はグラフの問題ととらえることが可能です。 それぞれの単語を、最初の \(3\) 文字を表す頂点から最後の \(3\) 文字を表す頂点へ張った有向辺として考えてみましょう。

まずそれぞれの単語を、最初の \(3\) 文字を表す頂点から最後の \(3\) 文字を表す頂点へ張った有向辺として考えます。すると、頂点数 \(52^3\)、 辺数 \(N\) の有向グラフが得られます。

ここで、問題を以下のように言い換えます。

有向グラフが与えられ、駒がいずれかの頂点に置かれている。 高橋君と青木君は交互に、駒が置かれている頂点から出ている有向辺を一つ選んでその先の頂点へ駒を移動させる。 操作ができなくなった方が負ける。 全ての頂点に対して、その頂点に駒が置かれている状態からゲームを始めたときの勝敗を判定せよ。

この問題は、後退解析と呼ばれるアルゴリズムを用いることで解くことができます。まず、勝ちの頂点と負けの頂点と引き分けの頂点を定義しましょう。

• 一本も有向辺が出ていない頂点は負けの頂点である。
• 有向辺が全て勝ちの頂点に出ているような頂点も負けの頂点である。
• 負けの頂点に出ている有向辺が1つでも存在するような頂点は勝ちの頂点である。
• 上の3つをいずれも満たさない頂点は全て引き分けの頂点である。

勝ち負けが確定した頂点が増えるごとに、その頂点に向かう辺が存在するすべての頂点に対して勝ち負けが確定しているかを判定していきます。毎回愚直に判定していると \(Θ(N^2)\) かかってしまいますが、\(\mathrm{queue}\) などを用いて実装することで \(O(N)\) で解けます。

#include<bits/stdc++.h>
using namespace std;
int M = 52 * 52 * 52;
int char_to_int(char c){
    if('A'<=c && c<='Z') return c-'A';
    else return c-'a'+26;
}
int string_to_int(char a,char b,char c){
    return char_to_int(a) * 52 * 52 + char_to_int(b) * 52 + char_to_int(c);
}

int main(){
    int N; cin >> N;
    vector<pair<int,int>> edge(N);
    vector<vector<int>> revGraph(M);
    vector<int> cnt(M);
    for(int i = 0; i < N; i++){
        string s; cin >> s;
        edge[i] = make_pair(string_to_int(s[0], s[1], s[2]), string_to_int(s[s.size()-3], s[s.size()-2], s[s.size()-1]));
        cnt[edge[i].first]++;
        revGraph[edge[i].second].push_back(edge[i].first);
    }
    vector<int> ans(M, -1);
    queue<int> que;
    for(int i = 0; i < M; i++) if(cnt[i] == 0){
        ans[i] = 0;
        que.push(i);
    }
    while(!que.empty()) {
        int t = que.front(); que.pop();
        for(int x : revGraph[t]) if(ans[x] == -1) {
            cnt[x]--;
            if(ans[t] == 0){
                ans[x] = 1; que.push(x);
            }
            else if(cnt[x] == 0){
                ans[x] = 0; que.push(x);
            }
        }
    }
    for(int i = 0; i < N; i++) {
        if(ans[edge[i].second] == -1) cout << "Draw" << endl;
        if(ans[edge[i].second] == 0) cout << "Takahashi" << endl;
        if(ans[edge[i].second] == 1) cout << "Aoki" << endl;
    }
}