東京工業大学プログラミングコンテスト2015 : M - コインと無向グラフ

これ定番テクだったりするのかな？
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_m

問題

N頂点M無向辺のグラフが与えられる。
各点にはC[i]枚のコインがある。
ここで２人で交互にコインを移動するゲームを行う。

自分の手番では以下のルールでコインを移動する。

• 0番以外のコインがある頂点を選択する
• その頂点のコインのうち、１枚以上を選び、0番に近い隣接点のどれか１個に移動する。

自分の手番でそれ以上移動できなくなったら負けである。
両者が最適手を取るとき、勝者はどちらか。

解法

自力で正答にたどり着けず、他の解法を参考に解答。
一応理屈は理解したつもりなので以下紹介。

この問題はNimの変形であることはすぐに思いつく。
コインの総数が多すぎるので、コイン枚数ごとにGrundy数を求めるのは無理である。
よって、なんとかこの問題をNimに落とし込みたい。

0番の頂点から偶数の距離にコインが何枚かある状態を考える。
先手がそのうち何枚かを0番に向けて移動すると、後手はその移動した何枚かのコインをさらに0番に向けて移動することを考える。
こうすると、先手は常に各コインが偶数の距離にある状態で手番が回ってくる。
言い換えると、先手は必ず負ける。

よって先手が勝つにはコインが奇数の距離にあるものをうまく使うしかない。
距離が３以上の奇数にあるコインは、先ほどの理屈に則ると結局先手後手の手番で２ずつ動くことになる。
よって最終的には距離１にある状態と等しくなる。

各コインが距離１にある場合、このゲームは単なるNimになるのでxorを使う定番手法が使える。
まとめると、距離が奇数にある頂点に対し、コイン枚数のxorを取ればよい。

int N,M,C[101010];
vector<int> E[101010];
int D[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>C[i],D[i]=101010;
	
	FOR(i,M) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	queue<int> Q;
	D[0]=0;
	Q.push(0);
	while(Q.size()) {
		int cur = Q.front();
		Q.pop();
		FORR(r,E[cur]) if(D[r]>D[cur]+1) D[r]=D[cur]+1, Q.push(r);
	}
	ll a=0;
	FOR(i,N) if(D[i]%2) a ^= C[i];
	if(a==0) _P("Second\n");
	else _P("First\n");
}

まとめ

言われてみればなるほどだけど、自力で思いつける気がしないな…。