AtCoder ARC 038 D - 有向グラフと数 (4D, 試験管赤色)

後退解析を用いる問題。queue に不慣れなので、急に queue を使えるように。

問題へのリンク

問題概要

頂点 辺の有向グラフが与えられる。各頂点 には値 X_v が割り振られている。先手と後手とで以下の対戦を行う

• スタート時には駒を頂点 1 に置く
• 各プレイヤーは各ターンにおいて
  • 駒をどこかに移動させる (グラフの辺に沿って)
  • ゲームを終了宣言する
• 双方ともに終了宣言しないまま後手が 10⁹ 回目のプレイをしたならばその時点でゲームは強制終了する

ゲームを終了宣言された時点での駒の置いてあるノードの値 がこのゲームにおける得点となる。先手は得点を最大化したくて、後手は得点を最小化したい。双方最善を尽くしたときの得点を求めよ。

制約

• 
• 

解法

以下の記事に書いた

• ゲームを解く

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// グラフの頂点数、辺数、各ノードの重み
int N, M;
vector<int> X;

// ゲームグラフ (後退解析のために辺の向きを逆にする)
vector<vector<int> > G;
vector<int> deg; // ゲームグラフにおける出次数 (辺の向きを逆にした状態で入次数)

// 二分探索判定 (D 以上にできるかどうか)
bool judge(int D) {
    vector<int> cdeg = deg;
    queue<int> que; // キュー
    vector<int> dp(N * 2, -1); // 最初は全体を -1 で初期化
    vector<bool> seen(N * 2, 0); // すでにみたか
    
    // 初期条件
    for (int i = 0; i < N; ++i) {
        if (X[i] >= D) {
            dp[i] = 1; // 先手勝ち
            que.push(i); seen[i] = true;

            if (cdeg[i] == 0) {
                dp[i + N] = 0; // 後手負け
                que.push(i + N); seen[i + N] = true;
            }
        }
        else {
            dp[i + N] = 1; // 後手勝ち
            que.push(i + N); seen[i + N] = true;

            if (cdeg[i] == 0) {
                dp[i] = 0; // 先手負け
                que.push(i); seen[i] = true;
            }
        }
    }   

    // 後退解析 (ここは自動的に書ける)
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (auto nv : G[v]) {
            if (seen[nv]) continue;
            --cdeg[nv]; // 辺 (nv, v) を削除
            if (dp[v] == 0) {
                dp[nv] = 1;
                que.push(nv); seen[nv] = true;
            }
            else if (dp[v] == 1) {
                if (cdeg[nv] == 0) {
                    dp[nv] = 0;
                    que.push(nv); seen[nv] = true;
                }
            }
        }
    }

    // ノード 0 が先手番で勝ちかどうか
    return (dp[0] == 1);
}

int main() {
    // 入力
    cin >> N >> M;
    X.resize(N*2);
    for (int i = 0; i < N; ++i) cin >> X[i];
    for (int i = 0; i < N; ++i) X[i+N] = X[i];
    G.assign(N*2, vector<int>());
    deg.assign(N*2, 0);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[b + N].push_back(a); // 後手番での後退遷移
        G[b].push_back(a + N); // 先手番での後退遷移
        deg[a]++; deg[a + N]++;
    }

    // 二分探索
    int low = 0, high = 1000000007; // low: 絶対先手勝つ、high: 絶対先手負ける
    while (high - low > 1) {
        int mid = (low + high) / 2;
        if (!judge(mid)) high = mid;
        else low = mid;
    }
    cout << low << endl;
}