Codeforces #746 Div2 : E. Bored Bakry

一応本番にも解けているな。
https://codeforces.com/contest/1592/problem/E

問題

整数列Aが与えられる。
Aの部分列A[L...R]のうち、全要素のbitwise-andを取った値がbitwise-xorを取った値より大きくなるものがあれば、その区間長の最大値を求めよ。

解法

0/1の2値を取る数列で、全要素のbitwise-andを取った値がbitwise-xorを取った値と比べ

• より大きい：1が偶数個、0が0個の場合ののみである。
• より小さい：1が奇数個、0が1つ以上の場合である。
• 等しい：1が偶数個・0が1つ以上、または1が奇数個、0が0個の場合

となる。

よって、Lを大きい順に走査し、その際A[i]の2進数表記の各bitにおいて、indexが奇数・偶数の時の最寄りの0の位置を覚えておこう。
そしてLに対してRの最大値を求める。その場合は、j bit目より上では「等しい」判定となり、j bit目では「より大きい」と判定されるRを各jに対し確認していくと良い。

int N;
int A[1010101];
int sum;
int C[2][1<<20][20];
int dis[20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) scanf("%d",&A[i]);
	int ma=0;
	FOR(j,20) {
		C[N%2][0][j]=N;
		dis[j]=N;
	}
	for(i=N-1;i>=0;i--) {
		sum^=A[i];
		FOR(j,20) {
			if(A[i]&(1<<j)) {
				if(C[i%2][sum>>j][j]>dis[j]) C[i%2][sum>>j][j]=0;
				ma=max(ma,C[i%2][sum>>j][j]-i);
				C[i%2][sum>>j][j]=max(C[i%2][sum>>j][j],i);
			}
			else {
				dis[j]=i;
				C[i%2][sum>>j][j]=i;
			}
		}
		
	}
	
	
	cout<<ma<<endl;
}

まとめ

入力の大きいときは、TLが2秒より大きいのはありがたいね。