Google Code Jam 2019 Round1C : Bacterial Tactics

問題. Bacterial Tactics

縦 $R$ 行，横 $C$ 列の長方形のマス目が与えられる．各マスは空白か危険な物質が置かれている．2人のプレイヤーが交互に空白のマスを選び V型かH型のバクテリアを置くことを繰り返す．V型バクテリアは置かれたマスの隣接する上下方向の空白マスか危険な物質があるマスに順番に複製して伝搬する．ただし，危険な物質が置かれているマスにバクテリアが伝搬すると，その手を選択したプレイヤーの負けとする．同様に，H型バクテリアは水平方向に伝搬する．また，バクテリアを置くことのできないプレイヤーも負けとする．2人のプレイヤーが最適な戦略で行動したときにどちらが勝つかを判定せよ．先手番が勝つときには，初手で勝つことのできる選択肢の数も答えよ．

制約： $1 \le R, C \le 15$

解法．グランディ数＋動的計画法＋累積和

このゲームは不偏ゲームなのでグランディ数に帰着することを考える．1つのマスにバクテリアを置くと1つまたは2つの矩形領域に分割される．そこで，任意の部分矩形領域 $S$ に1つのグランディ数 $\mathscr{g}(S)$ を対応させることを考える． $S$ 内でバクテリアを置くことができるマス $(r, c)$ に対して， $(r, c)$ によって分割される部分領域 $S_{1}, S_{2}$ から新たなグランディ数 $\mathscr{g}_{r c} = \mathscr{g}(S_{1}) \oplus \mathscr{g} (S_{2})$ を再帰的に求める．ただし，二項演算 $\oplus$ はビットごとの排他的論理和である．1マスからなる矩形領域のグランディ数は，空白なら 1 ，危険な物質があるときは 0 とする． $S$ 内のバクテリアを置くことができるマスの集合を $f(S)$ とすると， $\mathscr{g(S)} = \mathrm{mex}_{(r, c) \in f(S)} ( \mathscr{g}_{r c} )$ となる．ただし，任意の非負整数からなる集合 $X$ に対して $\mathrm{mex} (X)$ は $X$ の最小除外値（ minimum excluded value; mex ）を表している．

後は，領域を状態として動的計画法を行えばすべての部分矩形領域のグランディ数を求めることができる．このとき，マスにバクテリアを置けるかどうかを判定するのに，危険な物質が置かれている数に関する累積和を前もって求めることによって定数時間で判定できる．

計算時間： $O(N^6 \log N)$ （ $N = \max(R, C)$ )

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

/********************************************************************/
class Solver {
public:
    Solver(int _n) : num_case(_n) {}

    void input() {
        cin >> R >> C;
        b.resize(R);
        for (auto &x : b) cin >> x;
    }
    void solve();
    void print() { cout << "Case #" << num_case << ": " << num_win << '\n'; }

private:
    // define variable
    const int num_case;
    int R, C, num_win;
    vector<string> b;

    int nim[17][17][17][17];
    int cnt[17][17];

    void init() {
        num_win = 0;
        for (int r1 = 0; r1 < R; ++r1)
            for (int r2 = 0; r2 < R; ++r2)
                for (int c1 = 0; c1 < C; ++c1)
                    for (int c2 = 0; c2 < C; ++c2)
                        nim[r1][r2][c1][c2] = -1;

        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                if (b[r][c] == '#') cnt[r][c] = 1;
                else cnt[r][c] = 0;
            }
        }
        for (int r = 0; r < R; ++r)
            for (int c = 1; c < C; ++c)
                cnt[r][c] += cnt[r][c - 1];

        for (int c = 0; c < C; ++c)
            for (int r = 1; r < R; ++r)
                cnt[r][c] += cnt[r - 1][c];
    }

    int Count(const int r1, const int r2,
               const int c1, const int c2) {
        int res = cnt[r2][c2];
        if (1 <= c1) res -= cnt[r2][c1 - 1];
        if (1 <= r1) res -= cnt[r1 - 1][c2];
        if (1 <= c1 && 1 <= r1) res += cnt[r1 - 1][c1 - 1];
        return res;
    }

    int Divide(const int r1, const int r2,
                const int c1, const int c2) {
        if (r2 < r1 || c2 < c1) return 0;
        else if (r1 == r2 && c1 == c2) return b[r1][c1] == '.';

        int &res = nim[r1][r2][c1][c2];
        if (res != -1) return res;

        set<int> mex;
        for (int r = r1; r <= r2; ++r) {
            for (int c = c1; c <= c2; ++c) {
                if (b[r][c] == '#') continue;

                // (r, c) に H を置く
                if (Count(r, r, c1, c2) == 0) {
                    int grundy = 0;
                    if (r != r1) grundy ^= Divide(r1, r - 1, c1, c2);
                    if (r != r2) grundy ^= Divide(r + 1, r2, c1, c2);
                    mex.insert(grundy);
                }

                // (r, c) に V を置く
                if (Count(r1, r2, c, c) == 0) {
                    int grundy = 0;
                    if (c != c1) grundy ^= Divide(r1, r2, c1, c - 1);
                    if (c != c2) grundy ^= Divide(r1, r2, c + 1, c2);
                    mex.insert(grundy);
                }
            }
        }

        if (mex.size() == 0 || 1 <= *mex.begin()) res = 0;
        else {
            res = -1;
            for (const auto &x : mex) {
                if (res + 1 != x) break;
                else res = x;
            }
            ++res;
        }

        return res;
    }
};


void Solver::solve() {
    init();

    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            if (b[r][c] == '#') continue;

            // (r, c) に H を置く
            if (Count(r, r, 0, C - 1) == 0) {
                int grundy = 0;
                if (r != 0) grundy ^= Divide(0, r - 1, 0, C - 1);
                if (r != R - 1) grundy ^= Divide(r + 1, R - 1, 0, C - 1);
                if (grundy == 0) ++num_win;
            }

            // (r, c) に V を置く
            if (Count(0, R - 1, c, c) == 0) {
                int grundy = 0;
                if (c != 0) grundy ^= Divide(0, R - 1, 0, c - 1);
                if (c != C - 1) grundy ^= Divide(0, R - 1, c + 1, C - 1);
                if (grundy == 0) ++num_win;
            }
        }
    }
}
/********************************************************************/

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(4) << setiosflags(ios::fixed);

    int T; cin >> T;
    for (int i_case = 1; i_case <= T; ++i_case) {
        Solver s(i_case);
        s.input();
        s.solve();
        s.print();
    }

    return 0;
}

上では領域 $S$ に対してバクテリアを置くことのできるマス全体 $f(S)$ の要素を全部調べていたが，同じ行または同じ列のマスに対するグランディ数は同じになるので，行と列に対してのみ調べればよいことが分かる．これによって， $O(N^6 \log N)$ 時間から $O(N^5 \log N)$ 時間に改善できた．また，最小除外値の計算に set を使用していたが，領域 $S$ のグランディ数はその行数と列数の和以下になるのでビンソートで求めると高速化できる．これによって， $O(N^5 \log N)$ 時間から $O(N^5)$ 時間に改善できた．

計算時間： $O(N^5)$ （ $N = \max(R, C)$ )

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

/********************************************************************/
class Solver {
public:
    Solver(int _n) : num_case(_n) {}

    void input() {
        cin >> R >> C;
        b.resize(R);
        for (auto &x : b) cin >> x;
    }
    void solve();
    void print() { cout << "Case #" << num_case << ": " << num_win << '\n'; }

private:
    // define variable
    const int num_case;
    int R, C, num_win;
    vector<string> b;

    vector<vector<vector<vector<int>>>> nim;
    vector<vector<int>> cnt;

    int Divide(const int r1, const int r2, const int c1, const int c2);

    void init() {
        num_win = 0;

        nim.resize(R, vector<vector<vector<int>>>(R,
                      vector<vector<int>>(C, vector<int>(C, -1))));
        cnt.resize(R + 1, vector<int>(C + 1));

        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                if (b[r][c] == '#') cnt[r + 1][c + 1] = 1;

        for (int r = 1; r <= R; ++r)
            for (int c = 1; c <= C; ++c)
                cnt[r][c] += cnt[r][c - 1];

        for (int c = 1; c <= C; ++c)
            for (int r = 1; r <= R; ++r)
                cnt[r][c] += cnt[r - 1][c];
    }

    int Count(const int r1, const int r2,
               const int c1, const int c2) {
        return cnt[r2 + 1][c2 + 1] - cnt[r2 + 1][c1] - cnt[r1][c2 + 1] + cnt[r1][c1];
    }
};

int Solver::Divide(const int r1, const int r2,
           const int c1, const int c2) {
    if (r2 < r1 || c2 < c1) return 0;
    else if (r1 == r2 && c1 == c2) return b[r1][c1] == '.';

    int &res = nim[r1][r2][c1][c2];
    if (res != -1) return res;

    vector<bool> mex((r2 - r1 + 1) + (c2 - c1 + 1) + 1);
    for (int r = r1; r <= r2; ++r) {
        // r 行に H を置く
        if (Count(r, r, c1, c2) == 0) {
            size_t grundy = 0;
            if (r != r1) grundy ^= Divide(r1, r - 1, c1, c2);
            if (r != r2) grundy ^= Divide(r + 1, r2, c1, c2);
            if (grundy < mex.size()) mex[grundy] = true;

            if (r1 == 0 && r2 == R - 1 && c1 == 0 && c2 == C - 1 && grundy == 0)
                num_win += c2 - c1 + 1;
        }
    }

    for (int c = c1; c <= c2; ++c) {
        // c 列に V を置く
        if (Count(r1, r2, c, c) == 0) {
            size_t grundy = 0;
            if (c != c1) grundy ^= Divide(r1, r2, c1, c - 1);
            if (c != c2) grundy ^= Divide(r1, r2, c + 1, c2);
            if (grundy < mex.size()) mex[grundy] = true;

            if (r1 == 0 && r2 == R - 1 && c1 == 0 && c2 == C - 1 && grundy == 0)
                num_win += r2 - r1 + 1;
        }
    }

    for (size_t i = 0; i < mex.size(); ++i)
        if (!mex[i]) { res = i; break; }

    return res;
}

void Solver::solve() {
    init();
    if (R == 1 && C == 1 && b[0][0] == '.') num_win = 2;
    else Divide(0, R - 1, 0, C - 1);
}
/********************************************************************/

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(4) << setiosflags(ios::fixed);

    int T; cin >> T;
    for (int i_case = 1; i_case <= T; ++i_case) {
        Solver s(i_case);
        s.input();
        s.solve();
        s.print();
    }

    return 0;
}