AtCoder ARC #145 : E - Adjacent XOR

逆を考えるのはよくありそう。
https://atcoder.jp/contests/arc145/tasks/arc145_e

問題

N要素の整数列A,Bが与えられる。
整数Kを指定し、2≦i≦Kに対しA[i]=A[i] xor A[i-1]で同時に置き換えることを考える。
Aの最大値をMとすると、この作業をN*logM回程度行い、AをBに一致させられるか。

解法

逆演算を考え、BをAに一致させることを考える。
Bの末尾から合わせていくことを考えると、1要素あたりlogM程度の処理で合わせられればいいことになる。

B[i]をA[i]に合わせるとき、B[1]～B[i-1]における基底ベクトルの合成で、B[i]とA[i]の差分を作れればよい。

int N;
ll A[2020],B[2020];
vector<int> R;

void go(int r) {
	R.push_back(r);
	int i;
	for(i=1;i<=r;i++) B[i]^=B[i-1];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	
	for(i=N-1;i>=0;i--) if(A[i]!=B[i]) {
		vector<pair<ll,int>> D;
		ll dif=A[i]^B[i];;
		FOR(j,i) {
			ll a=B[j];
			FORR2(v,j,D) a=min(a,a^v);
			if(a) {
				D.push_back({a,j});
				dif=min(dif,a^dif);
			}
		}
		if(dif) {
			cout<<"No"<<endl;
			return;
		}
		
		for(j=D.size()-1;j>=0;j--) {
			ll v=A[D[j].second];
			ll tar=A[i];
			FOR(x,i+1) tar^=B[x];
			
			vector<ll> NB;
			FOR(x,j+1) {
				ll w=B[D[x].second];
				FORR(nv,NB) w=min(w,w^nv);
				NB.push_back(w);
				if(x!=j) tar=min(tar,tar^w);
			}
			if(tar) go(D[j].second+1);
		}
		
		go(i);
	}
	
	reverse(ALL(R));
	cout<<"Yes"<<endl;
	cout<<R.size()<<endl;
	FORR(r,R) cout<<r+1<<" ";
	cout<<endl;
}

まとめ

解答を見てしまうと難しくなさそうだが、本番正答者少ないし本番中に考えつくのは難しそう。