yukicoder : No.2658 L-R Nim

意外とコードは短い。
https://yukicoder.me/problems/no/2658

問題

N要素の整数列Aと整数Kが与えられる。
先手が、Aのうち1要素を選び±Kの範囲で値を増減できるとする(ただし増減後の値は正でなければならない)
その後、後手はAの連続部分列を選ぶ。
そしてその連続部分列に対しNimをプレイする。

先手が必勝となるような値の増減法はあるか判定せよ。

解法

Aのprefix xorをBとしたとき、B[0]～B[N]に重複がなければよい。
ここで、A[i]を1つ±K変更したとき、Kが小さいためxorの値の変更パターンは限定的である。
よって、あり得るxorの変更パターンを列挙し、また変更の入る位置を総当たりしながら、B[0]～B[N]に重複がないか探そう。

int N,K,A[101010];
set<int> S[50505];
vector<int> cand;
int X[50505];
int M[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i];
		X[i+1]=X[i]^A[i];
		for(j=-K;j<=K;j++) if(A[i]+j>=1) {
			S[i].insert(A[i]^(A[i]+j));
			cand.push_back(A[i]^(A[i]+j));
		}
	}
	sort(ALL(cand));
	cand.erase(unique(ALL(cand)),cand.end());
	
	FORR(c,cand) {
		int num=0;
		FOR(i,N+1) {
			if(M[X[i]]++==0) num++;
		}
		
		for(i=N-1;i>=0;i--) {
			if(--M[X[i+1]]==0) num--;
			if(M[X[i+1]^c]++==0) num++;
			if(num==N+1&&S[i].count(c)) {
				cout<<"Yes"<<endl;
				return;
			}
		}
		M[0]--;
		FOR(i,N) M[X[i+1]^c]=0;
	}
	cout<<"No"<<endl;
	
	
}

まとめ

Kが小さいと、(Aの値を問わず)xorの変更パターンが割と少ないんだな。