Codeforces #334 Div1 C. Lieges of Legendre

なんとか解けて良かった。Hackも出来たし。
http://codeforces.com/contest/603/problem/C

問題

N個の正整数A[i]が与えられる。
正整数Kが与えられた状態で、2人で以下のゲームを行う。

2人は交互に手番が回ってくる。
自分の手番では以下のどちらかを行う。

• A[i]のうち正のものを1つ選び、１減らす。
• A[i]のうち正偶数のものを1つ選び、それを消滅させる。代わりにA[i]/2の値をK個追加する。

自分の手番で全部の整数を0にしたものが勝者となる。
最適手を取った場合、勝者はどちらになるか。

解法

整数pのGrundy数G(p)を求めることを考える。
Kが偶数の場合、2つ目の手を取った場合、同じ要素が偶数個に分裂するので、それらのGrundy数のxorは0と見なせる。
よってKの偶奇で処理を分けよう。

それぞれ、pが小さい範囲について実際にG(p)を求めてみると、以下のことがわかる。

• Kが偶数の場合:
  • G(0)=0, G(1)=1, G(2)=2, p>=3の場合、pが奇数ならG(p)=0、偶数ならG(p)=1
• Kが奇数の場合：
  • G(0)=0, G(1)=1, G(2)=0, G(3)=1, G(4)=2, G(5)=0, G(6)=2, ...
  • pが4以上の場合、pが奇数ならG(p)=0、pが偶数ならG(p)は1か2

pに対しG(p)を求めるのが面倒なのは、Kが奇数でpが4以上の偶数の場合だけである。
G(p)を求めるにはG(p-1)とG(p/2)が必要だが、pが偶数ならG(p-1)は0確定なのでG(p/2)を順次求めていけば良い。
よってG(p)はO(log p)あれば求められる。

これでK,pに寄らずGrundy数の求め方が分かったので、あとはNimとして考えるだけ。

int N,K;
int A[101010];
int grund[13000];

int dodo(int v) {
	
	if(v<=30) return grund[v];
	if(v%2==1) return 0;
	if(v/2%2==1) return 1;
	return 3-dodo(v/2);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll xo=0;
	cin>>N>>K;
	for(i=1;i<=50;i++) FOR(j,3) {
		if(grund[i-1]==grund[i]) grund[i]++;
		if(i%2 && grund[i]==((K%2)?grund[i/2]:0)) grund[i]++;
	}
	
	FOR(i,N) {
		cin>>A[i];
		if(K%2==0) {
			if(A[i]==1) xo^=1;
			else if(A[i]==2) xo^=2;
			else xo ^= (A[i]%2)^1;
		}
		else {
			xo ^= dodo(A[i]);
		}
	}
	
	if(xo==0) _P("Nicky\n");
	else _P("Kevin\n");
	
}

まとめ

G(2)がひっかけになっていて、これで2Hack取れた。