mayoko’s diary

プロコンとかいろいろ。

SRM 676 div1 med: BoardEscape

解法

k が小さければ, このゲームは grundy 数を使った Nim にすることが出来ます。
grundy[k][i][j] = (あと k 回動かすことが出来て座標が (i, j) であるような場合の grundy 数) というのを, メモ化再帰で求めるイメージです。
ただ, この問題では k の上限が 10^9 と大きく, 上の grundy 数を素直に求めるだけでは間に合わないので, grundy[k][i][j] が k について周期的になっていそうなことを利用します(周期的なことの証明, 多分各セルの周りにあるセルについて場合分けすると証明できるんだと思います)。

各 k について, grundy[k][i][j] を求めます。周期的なので, ある整数 a, b が存在して, 任意の i, j について grundy[a][i][j] = grundy[b][i][j] が成り立つはずです。この a, b を利用して, k を常識的な範囲の数にすれば OK です。

vector<string> S;
int g[2600][55][55];

int grundy(int y, int x, int rest) {
    int& ret = g[rest][y][x];
    if (rest == 0 || S[y][x] == '#' || S[y][x] == 'E') return ret = 0;
    if (ret >= 0) return ret;
    set<int> s;
    int H = S.size(), W = S[0].size();
    for (int k = 0; k < 4; k++) {
        int ny = y+dy[k], nx = x+dx[k];
        if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
        if (S[ny][nx] == '#') continue;
        s.insert(grundy(ny, nx, rest-1));
    }
    ret = 0;
    while (1) {
        if (s.find(ret) == s.end()) return ret;
        else ret++;
    }
    return ret;
}

class BoardEscape {
public:
    string findWinner(vector <string> s, int K) {
        S = s;
        int H = S.size(), W = S[0].size();
        memset(g, -1, sizeof(g));
        map<vector<vi>, int> mp;
        int start, cycle;
        for (int k = 0; ; k++) {
            for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
                if (S[i][j] != '#') grundy(i, j, k);
            }
            vector<vi> G(H, vi(W));
            for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
                G[i][j] = g[k][i][j];
            }
            auto it = mp.find(G);
            if (it != mp.end()) {
                start = mp[G];
                cycle = k-start;
                break;
            } else {
                mp[G] = k;
            }
        }
        if (start > K) {
            int nim = 0;
            for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) if (S[i][j]=='T') nim ^= g[K][i][j];
            if (nim) return "Alice";
            else return "Bob";
        } else {
            int c = (K-start)%cycle;
            int nim = 0;
            for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) if (S[i][j]=='T') nim ^= g[start+c][i][j];
            if (nim) return "Alice";
            else return "Bob";
        }
    }
};