Codeforces #687 Div1 B. XOR-gun

本番割とすんなり解答できてるな。
https://codeforces.com/contest/1456/problem/B

問題

単調増加な数列Aが与えられる。
これらの数列に対し、連続する2要素を選択して、それらをxorを取った1要素に置き換える、という処理を任意に行えるとする。
Aを単調増加でなくすには、最小何手必要か。

解法

A中でMSBが一致する要素が3個以上連続してれば、後ろ2要素のxorを取れば単調増加でなくなるので1手で良い。
そうでない場合、Aは高々O(log(max(A)))要素程度しかないので、連続する2区間を総当たりし、xorを取って区間内を圧縮していくと大小関係が判定するようなものを探せばよい。

int N;
int A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	map<int,int> M;
	FOR(i,N) {
		cin>>A[i];
		x=-1;
		FOR(j,30) if(A[i]&(1<<j)) x=j;
		M[x]++;
		if(M[x]>=3) {
			cout<<1<<endl;
			return;
		}
	}
	
	int mi=101010;
	FOR(y,N) FOR(x,y) {
		ll X=0;
		for(i=0;x-i>=0;i++) {
			X^=A[x-i];
			ll Y=0;
			for(j=0;y+j<N;j++) {
				Y^=A[y+j];
				if(X>Y) mi=min(mi,i+j);
			}
		}
	}
	
	
	if(mi==101010) mi=-1;
	cout<<mi<<endl;
}

まとめ

こういう1つの条件をクリアするとその時点で配列長の上限が小さくなるので、別の手が打てるっていうの、工夫のし甲斐があって割と好きだな。