AOJ 2339: 問題文担当者は働かない！

Person responsible for problem description don't w

解法

grundy数のベクトルで考える.
ある頂点 u から出る辺が存在しないとき r(u) := 0 と定義し,
u の子が存在するとき, r[u] := 「r(uの子の集合) に含まれない最小の自然数」
として, grundy数のベクトル d の第 i 成分を 「r(u) = i を満たす全ての u に対し, その頂点にある石の数 v(u) を全て xor したもの」とすると, d = 0 の時必敗で, そうでない時必勝である.

証明

d != 0 のとき, 必ず一手で d = 0 とできる.
d = 0 のとき, 一手で d = 0 とできない.
閉路が無いので必ずゲームが終了する.

コード

#include <bits/stdc++.h>
using namespace std;
#define N 1000
int i, n, m, v[N], r[N], d[N];
vector<int> g[N];

int dfs(int u){
	int &s = r[u];
	if(s >= 0) return s;
	set<int> t;
	for(int v: g[u]) t.insert(dfs(v));
	while(t.count(++s));
	return s;
}

int main(){
	scanf("%d%d", &n, &m);
	for(i = 0; i < n; i++) scanf("%d", v+i);
	for(i = 0; i < m; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		g[a-1].push_back(b-1);
	}
	memset(r, -1, sizeof(r));
	for(i = 0; i < n; i++) d[dfs(i)] ^= v[i];
	int w = 2;
	for(i = 0; i < n; i++)
		if(d[i]) w = 1;
	printf("%d\n", w);
	return 0;
}