ARC038 C-茶碗と豆 (100点)

【問題】
arc038.contest.atcoder.jp

【考察】
Grundy 数を使いそうなのはすぐに分かるのですが、普通に山ごとに Grundy 数を設定しようとすると、ある山の遷移が他の山に影響を与える設定のせいでうまくいきません。そこで視点を変えて、茶碗に入っている豆ごとに Grundy 数を定めることにします。つまり山から豆が減る (あるいは増える) ことを遷移と捉えるのではなく、ある豆が、入っている茶碗の C の値によって定められる範囲内でより左の茶碗に移動することを遷移と見るわけです。これなら互いの豆は干渉し合わないため、入っている茶碗を基準としてうまく Grundy 数を決めていくことができます。ただ解説にも述べられているんですが、存在する全ての豆について、Grundy 数の XOR をとっていこうとすると TLE して 80 点しか取れません。幸いなことに、同じ値を偶数回 XOR すると 0 になる (XOR の関わる問題の重要な性質だと思う) ことから、ある茶碗に入った豆全体の XOR は、その豆の数が偶数なら 0 で、奇数なら豆が 1 つのときの Grundy 数に一致することがわかります。これを使うことで O(N) で XOR を取っていくことが可能です。
満点 (104点) 解法は、セグツリを使うことまでは分かったけど、うまく実装できなかった。かなしい。

【コード】

vector<int> memo;
vector<P> z;
int grundy(int x) {
	if(x==0) return 0;
	if(memo[x]!=-1) return memo[x];
	set<int> q;
	REP(i,z[x-1].first) q.insert(grundy(x-(int)(i+1)));
	int g=0;
	while(q.count(g)!=0) ++g;
	return memo[x]=g;
}
int main() {
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	memo.resize(n);
	REP(i,n) memo[i]=-1;
	z.resize(n);
	REP(i,n-1) cin>>z[i].first>>z[i].second;
	int ret=0;
	REP(i,n-1) {
		if(z[i].second%2==1) ret=ret^grundy((int)i+1);
	}
	if(ret!=0) cout<<"First"<<endl;
	else cout<<"Second"<<endl;
}

【使ったアイデア】
Grundy 数は、状態が他の要素に依存しないような対象に対して設定する。同じ数で XOR を偶数回とると 0 になる。

【得た知見】
この問題を解くために蟻本のゲームの章を読んだ。