AOJ 2376: DisconnectedGame

問題

二人完全情報ゲームをする。
グラフが隣接行列で与えられる。交互に辺を追加していき、グラフを連結にしたほうの負けである。

解法

N(<=1000)で大きいので、全探索では解けない。
とりあえず、Union-Find木を用いて、既に連結になっている部分を調べる。
少し考察すると、(既に連結である部分の頂点数mod 4)を状態として持てば良いことが分かるが、mod 4で状態を持つと状態数が(1000^4)/24程度と多くなりすぎるため、もう少し賢い解法を考える必要がある。

クリークを作るための辺の数の差分の偶奇を考えると実は状態をmod 2で持てば良いことが分かり、状態数も1000^2程度に減る。
mod 2で状態を持った場合は、遷移先が高々2,3個しかしかなく、状態がループすることはない(辺の数は単調増加するので、ゲームが必ず終了する)のでgrundy数で解くことができる。

コード

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <set>
using namespace std;
 
#define N 1000
struct UF {
	int par[N];
	
	void init(int n){
		for(int i = 0; i < n; i++){
			par[i] = i;
		}
	}
	
	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}
	
	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		par[x] = y;

	}
};
 
int grundy[N+10][N+10][2];
 
string s[2] = {"Taro", "Hanako"};
 
int solve(int a, int b, int c){
    if(grundy[a][b][c] >= 0) return grundy[a][b][c];
    set<int> st;
    if(a>=1 && a+b>2) st.insert(solve(a-1, b, !c));
    if(b>=2 && a+b>2) st.insert(solve(a+1, b-2, c));
    if(a+b==2) st.insert(solve(a, b, !c));
    for(int i = 0; ; i++){
        if(!st.count(i)){
            return (grundy[a][b][c] = i);
        }
    }
}
 
int main(){
    int n;
    cin>>n;
    vector<string> g(n);
    int a = 0;
	int sm = 0;
    UF uf;
    uf.init(n);
    for(int i = 0; i < n; i++){
        cin>>g[i];
        for(int j = 0; j < n; j++){
            if(g[i][j] == 'Y'){
				sm++;
                uf.unite(i, j);
            }
        }
    }
	a ^= (sm/2)&1;
    vector<int> d(n, 0);
    for(int i = 0; i < n; i++){
        d[uf.find(i)]++;
    }
    int sum[2] = {};
    for(int i = 0; i < n; i++){
        int b = d[i];
		if(b==0) continue;
        if(b&2) a ^= 1;
        sum[b%2]++;
    }
    memset(grundy, -1, sizeof(grundy));
    grundy[2][0][0] = grundy[0][2][0] = grundy[1][1][0] =  0;
     
    bool res = solve(sum[0], sum[1], a);
    cout<<(res?s[0]:s[1])<<endl;
 
    return 0;
}