MADMAX [Codeforces Round #459 Div.1 B]

http://codeforces.com/contest/917/problem/B

N頂点M辺のDAG（サイクルが無い有向グラフ）がある。
辺には英小文字が書いてある。
以下のゲームをする。

• Aさんが頂点iに、Bさんが頂点jに駒を置く
• Aさんが先手で交互に操作する
• 自分のターンでは自分の駒を今いる所から辺を辿って1つ動かす
• 使える辺は、その前（相手）に使われた辺にかかれている文字以上の文字の辺のみ
• 遷移できなくなったら負け

　
AさんとBさんの初期位置の組全てについて二人とも最適に動く時、A,Bのどちらが勝つかを答えよ。

前提知識

• 後方解析（or Grundy数）

解法

http://codeforces.com/contest/917/submission/34673736

以下Grundy数で解いているが、後方解析で普通に解ける。
以下の解説は、Grundy数の知識が無いと理解は難しい。
もし知らないとしたら、上のリンクなどで勉強してから以下の解説を見て欲しい。
ちなみに、この問題はGrundy数の練習問題にふさわしい。理解の定着にも使える。
　
ゲームの状態は「(i,j,c) := 自分の駒がiにあり、相手の駒がjにあり、最後にcの文字の辺が遷移に使われた時のgrundy数」
と考えるとO(100*100*26)なので状態的には大丈夫。
ここからの遷移も最大99個なので遷移数的にも大丈夫そう。
あとは、状態全てのgrundy数をメモ化再帰を使って計算し、それぞれ答えれば答え。

int N, M;
vector<pair<int, int>> E[101];
//---------------------------------------------------------------------------------------------------
int memo[101][101][30];
int gru(int i, int j, int c) {
    if (0 <= memo[i][j][c]) return memo[i][j][c];

    set<int> g;
    fore(p, E[i]) {
        int to = p.first;
        int cc = p.second;

        if (cc < c) continue;
        g.insert(gru(j, to, cc));
    }
    int res = 0;
    while (g.count(res)) res++;
    return memo[i][j][c] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b; char c; cin >> a >> b >> c;
        a--; b--;
        E[a].push_back({ b, c - 'a' });
    }

    rep(i, 0, N) rep(j, 0, N) rep(c, 0, 28) memo[i][j][c] = -1;

    rep(i, 0, N) {
        rep(j, 0, N) {
            if (gru(i, j, 0) == 0) printf("B");
            else printf("A");
        }
        printf("\n");
    }
}