yukicoder : No.669 対決!!! 飲み比べ

ちょっと間が空きました。
https://yukicoder.me/problems/no/669

問題

Nimの変形問題。
山にある石を任意個数でなく1～Kの間でのみ取り除くことができるとき、勝者はどちらか。

解法

良くあるGrundy数の計算をまともにやると、Grundy数計算にO(K*(山の石の最大数))程度かかりTLEする。
小さめの数字で試したり、もしくは再帰的に考えると石の個数Xの山のGrundy数はX % (K+1)になるので、あとはこれをもとにいわゆるNimを解くだけ。
以下のコードは10000程度までは愚直にGrundy数を求めている。

int N,K;
int A[1010];
int gr[1010100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	for(i=1;i<=10000;i++) {
		set<int> S;
		for(j=1;j<=min(K,i);j++) S.insert(gr[i-j]);
		while(S.count(gr[i])) gr[i]++;
	}
	for(i=10001;i<=1000000;i++) gr[i]=gr[i-(K+1)];
	
	int nim=0;
	FOR(i,N) {
		cin>>x;
		nim^=gr[x];
	}
	if(nim==0) cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
	
}

まとめ

実装は軽いけど、Grundy数の問題を★３未満にするにはちょっと戸惑うね。