AtCoder Regular Contest 038 D - 有向グラフと数

部分点解法はできたはずなのにもったいない。

問題

D: 有向グラフと数 - AtCoder Regular Contest 038 | AtCoder

解法

基本的にこれを参考にしました。
http://www.slideshare.net/chokudai

部分点解法は,ターン数がたかだか2*Nでも結果が変わらないのでゲーム木作ってmin-maxするだけ。

満点解法についてちょっと補足したいと思います。
二分探索してゴニョゴニョするというアイデアは大丈夫だと思いますがその二分探索のところでやってる後退解析は結構悩んだのでそこを説明します。

目標の点数がvalであるとします。まず最初に得点が確定するところは,

・X[i] >= valならば,先手がiにたどり着けば先手の勝ち確定
・X[i] < valならば,後手がiにたどり着けば後手の勝ち確定

iから行き着く先がないのであれば,さらに

・X[i] >= valであれば先手は勝ち確定,後手は負け確定
・X[i] < valであれば先手は負け確定,後手は勝ち確定

とわかります。このようにすでに結果が確定しているところをqueueに突っ込んでいきます。
すると,次のように探索すればそれぞれのノードが先手の勝ち確定 or 後手の勝ち確定なのかが判別できます。
・a -> bと移動できる時,bに行くと相手の負けが確定している(スライドで言う白)ならば自分は勝ち確定なので黒
・a -> bと移動できるとき,どのbに遷移しても相手の勝ちが確定している(スライドで言う黒)ならば自分は負け確定なので白
1つ目は簡単に判定できますが,2つ目はちょっと難しいです。どうやるかというと,

今までにa -> b(bは黒)となったbの数を覚えておく。これがaから遷移できる頂点の数と等しくなったら遷移できる頂点がすべて黒ということなので負け確定になる。ソースコードではnums[]という配列でそれを管理しています。

以下ソースコード

満点解法

const int MAXN = 111000;
int N, M;
int X[MAXN];
vi G[2*MAXN], rG[2*MAXN];

// -1だとまだわからない
// 0だと負け確定
// 1だと勝ち確定
int win[2*MAXN];
int nums[2*MAXN];

bool ok(int val) {
    memset(win, -1, sizeof(win));
    memset(nums, 0, sizeof(nums));
    queue<int> que;
    for (int i = 0; i < N; i++) {
        if (X[i] >= val) {
            win[i] = 1;
            que.push(i);
        } else {
            win[i+MAXN] = 1;
            que.push(i+MAXN);
        }
        if (G[i].size() == 0) {
            if (win[i] == -1) {
                win[i] = 0;
                que.push(i);
            }
            if (win[i+MAXN] == -1) {
                win[i+MAXN] = 0;
                que.push(i+MAXN);
            }
        }
    }
    while (!que.empty()) {
        int now = que.front(); que.pop();
        for (int next : rG[now]) {
            if (win[next] == -1 && win[now] == 0) {
                win[next] = 1;
                que.push(next);
            }
            if (win[next] == -1 && ++nums[next] == (int)G[next].size()) {
                win[next] = 0;
                que.push(next);
            }
        }
    }
    return win[0] == 1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> X[i];
    }
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b+MAXN);
        G[a+MAXN].push_back(b);
        rG[b+MAXN].push_back(a);
        rG[b].push_back(a+MAXN);
    }
    int low = 0, high = 1e9+3;
    while (high - low > 1) {
        int mid = (high+low) / 2;
        if (ok(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    cout << low << endl;
    return 0;
}

部分点解法

const int MAXN = 1111;
vector<int> G[MAXN];
int N, M;
int X[MAXN];

int dp[2*MAXN][MAXN][2];

int dfs(int v, int turn) {
    if (turn == 2*MAXN) return X[v];
    int player = turn%2;
    int& ret = dp[turn][v][player];
    if (ret >= 0) return ret;
    if (player == 0) {
        ret = X[v];
        for (int next : G[v]) {
            ret = max(ret, dfs(next, turn+1));
        }
        return ret;
    } else {
        ret = X[v];
        for (int next : G[v]) {
            ret = min(ret, dfs(next, turn+1));
        }
        return ret;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> X[i];
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
    }
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, 0) << endl;
    return 0;
}