AtCoder ABC #172 : F - Unfair Nim

いろいろ解がありそう。
https://atcoder.jp/contests/abc172/tasks/abc172_f

問題

整数列Aを用いてNimを行う。
残りが1以上残る範囲でA[0]を減らし、その分A[1]を増やして後手必勝となるようにしたい。
可能なら、最小いくつ減らせばよいかを求めよ。

解法

X=A[2]^A[3]^....とする。
0≦k＜A[0]としたとき、(A[0]-k)^(A[1]+k)^Xとなるkを求める問題となる。

解法はいろいろありそうだが、ここでは平方分割？を紹介。
kを0～(2**20-1)の範囲で総当たりし、(A[0]-k)^(A[1]+k)^Xの下位20bitが0となるkを求めよう。
次に、それらのkの候補に対し、上位20bitを総当たりする。

A[0]とA[1]の値によってはkの下20bitの候補が多数となるので、適度に探索を打ち切ったりするとよい。
ただ、値によっては下記コードTLEしそうだな。

int N;
ll A[303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	ll xo=0;
	for(i=2;i<N;i++) xo^=A[i];
	
	vector<int> cand;
	FOR(i,1<<20) if(i<A[0]) {
		ll v=(A[0]-i)^(A[1]+i)^xo;
		if((v&((1<<20)-1))==0) cand.push_back(i);
	}
	
	ll mi=1LL<<50;
	FORR(c,cand) {
		for(ll a=c;a<min(mi,A[0]);a+=1<<20) {
			ll v=(A[0]-a)^(A[1]+a)^xo;
			if(v==0) mi=min(mi,a);
		}
	}
	
	if(mi==1LL<<50) mi=-1;
	cout<<mi<<endl;
	
}

まとめ

ちょっと雑かも。