Codeforces #743 Div1 : B. Xor of 3

B問題からして難しめだったっぽい回。
https://codeforces.com/contest/1572/problem/B

問題

01で構成されるN要素の数列Aが与えられる。
連続する3要素を選択し、それらの値を、元の値のxorをとった値で同時上書きすることができるとする。
この手順を繰り返し、数列をすべて0にできるか。
できるならその手順の一例を示せ。

解法

この問題の手順を行っても数列全体のパリティは変わらない。
よって、元のパリティが奇数なら解なし。
そうでない場合必ず解がある。

Nの偶奇で場合分けする。

• Nが奇数の場合、中心となるindexを1,3,5...と行っていくと、奇数iに対しA[i]=A[i-1]となる。また、A[N-3]=A[N-2]~A[N-1]=0となる。その後、最後N-4,N-6,...,3.1と手順を繰り返すと全要素0になる。
• Nが偶数の場合、パリティが偶数となる奇数長のprefixと残りのsuffixに分け、上記手順をそれぞれ行えばよい。

int T;
int N;
int A[202020];
int B[202020];
 
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	FOR(x,T) {
		
		cin>>N;
		int num=0;
		FOR(i,N) {
			cin>>A[i];
			num^=A[i];
		}
		/*
		
		if(T>100) {
			if(x!=67) continue;
			FOR(i,N) cout<<A[i];
			cout<<endl;
		}
		*/
		if(num) {
			cout<<"NO"<<endl;
			continue;
		}
		vector<int> ret;
		
		if(N%2) {
			for(i=0;i<N-1;i+=2) ret.push_back(i+1);
			for(i=N-5;i>=0;i-=2) ret.push_back(i+1);
		}
		else {
			num=0;
			for(i=0;i<N;i++) {
				num^=A[i];
				if(num==0&&i%2==0) {
					for(j=0;j<i;j+=2) ret.push_back(j+1);
					for(j=i-4;j>=0;j-=2) ret.push_back(j+1);
					FOR(j,i+1) A[j]=0;
					
					for(j=N-3;j>=i;j-=2) ret.push_back(j+1);
					for(j=i+1;j<N-2;j+=2) ret.push_back(j+1);
					for(j=i;j<N;j++) A[j]=0;
					break;
				}
			}
			
			FOR(i,N) if(A[i]) break;
			if(i<N) {
				cout<<"NO"<<endl;
				continue;
			}
			
		}
		cout<<"YES"<<endl;
		cout<<ret.size()<<endl;
		FORR(r,ret) cout<<r<<" ";
		cout<<endl;
		
		
		
	}
}

まとめ

Nが偶数の時の解法面白いな。