Codeforces Round #406 (div.2) C

問題

http://codeforces.com/contest/787/problem/C

問題概要

円上に n 個のマスがある．それぞれ 0 から n-1 まで番号が振られている．
0 番目はブラックホールである．
また，どこかのマスに一匹のモンスターがいる．
これらを使って2人でゲームをする．2人はそれぞれ集合S1, S2を持っていて，要素はいくつかの自然数である．
順番に，自分の集合の中から好きな数字をえらんで，モンスターを今いる位置から時計回りに選んだ数字分移動させる．この時，ちょうどブラックホールにモンスターを移動させたほうが勝ちである．
モンスターの初期位置が 1, 2, …, n-1 番目のマスだった場合，2人のプレイヤーが最善を尽くした時に先手（プレイヤーは二人いるので2通り）は「勝ち」「ループ」「負け」のいずれになるかをすべて答えよ．

・制約
2 <= n <= 7000
1 <= |Si| <= n-1, for i = 1, 2

解法

典型DP．ゲームなので，最終状態からさかのぼっていくというのが定石．
手番とモンスターの位置で，2*n の状態が存在する．
dp[i][j] := 先手が i 人目で，モンスターの初期位置が j マス目だったときの先手の結果　とする．
dp[1][0] = dp[0][0] = (負け) としておく．
(手番, モンスター位置) = (0, 0) と (1, 0) を根とするDFSをやる．（BFSでも良い．そっちのほうが多かったように思う．）
今見ている状態が負けであれば，一つ前の状態（手番が入れ替わる）は勝ちと決まる．

どのように遷移しても相手が勝ってしまう（すべての次の状態が勝ち）ならば，今の状態を負けとする．
なので，今見ている状態が勝ちであれば，一つ前の状態の勝ちうる遷移の数を一つ減らす．遷移の方法は，自分の持っている自然数の集合のサイズ分あるが，これが0になってしまった場合は，先ほど述べた自分の負けの状態である．

DFSで次に探索しようとしている状態が勝ちとも負けとも今の段階で決められない場合は，そこで探索を保留する．

最終的に，勝ちとも負けとも決まらなかった状態は，ループの状態である．（勝てないのは明らかなので，負けるよりも無限ループさせるほうが最善手となる．）

計算量は O(n^2)．

ソースコード

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

constexpr int INF = 1e9;

int n;

// -1: current turn lose, 1: win, 0: visited(and not determined)
void dfs(int turn, int p, vector<vector<int>>& dp, vector<vector<int>>& cnt, vector<vector<int>> const& s) {
    if(dp[turn][p] == INF) {
        dp[turn][p] = 0;
    }
    for(auto x : s[turn^1]) {
        int np = (p - x + n) % n;
        if(dp[turn^1][np] != INF) {
            continue;
        }
        if(dp[turn][p] == -1) {
            dp[turn^1][np] = 1;
        } else if(--cnt[turn^1][np] == 0) {
            dp[turn^1][np] = -1;
        } else {
            continue;
        }
        dfs(turn^1, np, dp, cnt, s);
    }
}

int main() {
    cin >> n;
    vector<vector<int>> s(2);
    for(int i=0; i<2; ++i) {
        int k;
        cin >> k;
        s[i].resize(k);
        for(int j=0; j<k; ++j) {
            cin >> s[i][j];
        }
    }
    vector<vector<int>> dp(2, vector<int>(n, INF));
    vector<vector<int>> cnt(2, vector<int>(n));
    for(int i=0; i<2; ++i) {
        for(int j=0; j<n; ++j) {
            cnt[i][j] = s[i].size();
        }
    }
    dp[0][0] = dp[1][0] = -1;
    dfs(0, 0, dp, cnt, s);
    dfs(1, 0, dp, cnt, s);
    for(int i=0; i<2; ++i) {
        for(int j=1; j<n; ++j) {
            int r = dp[i][j];
            if(r == -1) {
                cout << "Lose";
            } else if(r == 1) {
                cout << "Win";
            } else {
                cout << "Loop";
            }
            cout << " \n"[j == n-1] << flush;
        }
    }
}

感想

最初，根を適当に選んで DFS していたせいで，ループをうまく扱えなくて困っていた．
こういうコードなんだけども，(DFS 部のみ抜粋）

int dfs(int p, vector<vector<int>>& dp, vector<vector<int>> const& s, int turn) {
    int& r = dp[turn][p];
    if(r != INF) {
        return r;
    }
    if(p == 0) {
        return r = -1;
    }
    r = 0;
    int t = 2;
    for(int i=0; i<s[turn].size(); ++i) {
        t = min(t, dfs((p+s[turn][i])%n, dp, s, (turn+1)%2));
    }
    return r = -t;
}

これだと以下の図のようなケース（不必要な辺は省いています）で死にます．

左下の状態は最終的に負けになって欲しいところですが，上のコードだとそうならない．
方針はわかってるのに解ききれなかったのは悔しい．