Codeforces #399 E. Game of Stones

Grundy数のよい典型問題。
http://codeforces.com/contest/768/problem/E

問題

N個の石の山があり、それぞれS[i]個の石からなる。
2人で交互に石を取り合うゲームを行う。
自分の手番では1つの山を選択し、いくつかの石を取り除く。
ただし、1つの山からは同じ個数を2回以上とることはできない。

自分の手番で石を取り除けない場合、負けとなる。
両者最適手を取った場合、勝者は先手後手どちらか。

解法

以下を考える。
f(x,mask) := 残り石の数がx個で、過去にmaskが示すような個数のとり方をしたことがある場合の、Grundy数
S[i]の上限が小さいため、maskに取りうる値はかなり限定的となるので、ありうるf(x,mask)を総当たりしてしまおう。

あとはNimの常とう手段通り、f(S[i],0)のxorを取ればよい。

int N;

map<ll,int> memo[61];

int go(int cur,ll mask) {
	if(cur==0) return 0;
	
	mask &= (1LL<<(cur+1))-1;
	if(memo[cur].count(mask)) return memo[cur][mask];
	
	int mex=0;
	set<int> SS;
	int i;
	for(i=1;i<=cur;i++) if((mask&(1LL<<i))==0) {
		SS.insert(go(cur-i,mask | (1LL<<i)));
	}
	
	while(SS.count(mex)) mex++;
	return memo[cur][mask]=mex;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=60;i++) go(i,0);
	
	int nim=0;
	scanf("%d",&N);
	FOR(i,N) scanf("%d",&x), nim^=memo[x][0];
	
	if(nim==0) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	
	
}

まとめ

f(x,0)は手元で求めて埋め込んでもよかったようだ。