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

解法にいたった経緯を時系列順に並べる。

• 小さいケースを確かめてみる。N=2、N=3、N=4…。

N=4、試すことすら困難。諦めざるを得ない。

• ちょっとグラフの形を変える

グラフが星だとxorで分かるのか。心底どうでもいい。

は？　なにこれ

n時間RucKyGAMESをしながらだらだらする。

• 何か他の形考えてみるか。

孤立点だったら完全にNimじゃん。そうかこの問題Nim含むのか。じゃあGrundyだな(確信)

• さっき試した小さいグラフでGrundyを試してみる。

どうやら多項式にしておくとよさげっぽい。次数どうなんだろ。
なんか次数がDAGのほうのGrundy数になるっぽいな？？

要はこの問題はやっぱりGrundy数で解けるんだけど、
DAGにおける各頂点のGrundy数をまず求めておくと、与えられた盤面のGrundy数は、

Σ{i} (Grundy数がiだった頂点に書かれた値全てのxor)ω^i

となり、これが0なら後手必勝。他は先手必勝。

ちゃんとした経路を踏んだらどうってことない問題だった。ただ問題の設定が設定なので試しにくすぎて変な方向に進みがち。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>g[1100];
int c[1100];
int deg[1100];
int grundy[1100];
void dfs(int a){
	vector<int> chi;
	for(int i=0;i<g[a].size();i++){
		if(!~deg[g[a][i]])dfs(g[a][i]);
		chi.push_back(deg[g[a][i]]);
	}
	std::sort(chi.begin(),chi.end());
	int next=0;
	for(int i=0;i<chi.size();i++){
		if(i&&chi[i]==chi[i-1])continue;
		if(chi[i]!=next)break;
		next++;
	}
	deg[a]=next;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",c+i);
	}
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
	}
	for(int i=0;i<a;i++){
		deg[i]=-1;
	}
	for(int i=0;i<a;i++){
		if(!~deg[i]){
			dfs(i);
		}
	}
	for(int i=0;i<a;i++)grundy[deg[i]]^=c[i];
	for(int i=0;i<1100;i++)if(grundy[i]){printf("1\n");return 0;}
	printf("2\n");
}