AOJ 2376 Disconnected Game - すいバカ日誌

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2376

解法

石取りゲームだからいい感じにわかるんでは？と思ったけどよくわかんなかったのでメモ化再帰で解きます．

勝ちが決まるタイミングはは，連結成分の数が2であり，かつ自分の手番で辺を追加すると，追加できる辺の数が 0 になるときですね．（それはそう）
それまでは，異なる連結成分を連結させるか，連結成分内の頂点同士に辺を張るかのどちらかです．

残りの辺の数は愚直にもたずに偶奇で判定できますね．異なる連結成分同士を結ぶ辺以外で使える辺の数を $unused$ とします．

異なる連結成分同士を結んだ時，$unused$ も変化しますが，偶奇だけわかればいいので，連結成分のサイズの偶奇の情報を持つだけでいいです．
今，サイズが奇数，偶数の連結成分の数を $(odd, even)$ とします．

$(odd, even, unused)$ でメモ化再帰します．
自分の手番でできるパターンは以下の4通りあります．

大きさが偶数の連結成分同士を結ぶ．結果として，偶数の連結成分が1つ減り，新たに使える辺が奇数本増える．
大きさが奇数の連結成分同士を結ぶ．結果として，奇数の連結成分が2つ減り，偶数の連結成分が1つ増える．また，使える辺の数が偶数本増える．
大きさが偶数と奇数の連結成分を結ぶ．結果として，偶数の連結成分が1つ減る．また，使える辺の数が奇数本増える．
連結成分同士を結ばないように辺を張る．

4つ目の場合はメモ化再帰でループが発生してしまいますが，実は $unused$ を偶数から奇数に移す場合は無視できます．
なぜなら，こういう操作をされた場合，次の手番の人が $unused$ を奇数から偶数に移せば，先ほどと同じ状態になるため，いずれは連結成分同士を結ぶ状況に陥るからです．（つまり偶数から奇数に移す操作が最善手であることはない．そういう状況はすでに負け確定．）
これでループが解消できたので，安心してかけます．

ソースコード

#include <bits/stdc++.h>
using namespace std;

int dfs(int v, vector<string> const& g, vector<bool>& visited) {
    visited[v] = true;
    int res = 1;
    for(int i = 0; i < (int)g.size(); ++i) {
        if(g[v][i] == 'Y' && !visited[i]) {
            res += dfs(i, g, visited);
        }
    }
    return res;
}

int rec(int odd, int even, int unused, vector<vector<vector<int>>>& dp) {
    int& res = dp[odd][even][unused];
    if(res != -1) {
        return res;
    }

    if(odd + even == 2) {
        return res = unused;
    }
    if(unused == 1 && !rec(odd, even, !unused, dp)) {
        return res = 1;
    }
    if(odd > 0 && even > 0 && !rec(odd, even - 1, !unused, dp)) {
        return res = 1;
    }
    if(odd >= 2 && !rec(odd - 2, even + 1, unused, dp)) {
        return res = 1;
    }
    if(even >= 2 && !rec(odd, even - 1, !unused, dp)) {
        return res = 1;
    }
    return res = 0;
}

int main() {
    int N;
    cin >> N;
    vector<string> g(N);
    for(int i = 0; i < N; ++i) {
        cin >> g[i];
    }

    vector<bool> visited(N);
    int odd = 0, even = 0;
    int unused = 0;
    for(int i = 0; i < N; ++i) {
        if(!visited[i]) {
            int C = dfs(i, g, visited);
            unused += C * (C - 1) / 2;
            if(C & 1) {
                ++odd;
            } else {
                ++even;
            }
        }
        for(int j = i + 1; j < N; ++j) {
            unused -= (g[i][j] == 'Y');
        }
    }
    unused %= 2;

    vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(N + 1, vector<int>(2, -1)));
    if(rec(odd, even, unused, dp)) {
        cout << "Taro" << endl;
    } else {
        cout << "Hanako" << endl;
    }
}

感想

4つ目のパターンを書き忘れた状態で間違えて提出してしまったんですが，なぜか通ってしまい，ジャッジのケースが弱いのか，実は完全に無視して良いのかよくわからなくなった…．
もしあるなら O(1) 解をもっと考えればそのうちわかるかも（考えませんけどね）．