Manthan Codefest 19 : F. Bits And Pieces

こういうのCSAcademyとかに多いイメージ。
https://codeforces.com/contest/1208/problem/F

問題

整数列Aが与えられる。
i＜j＜kであるような3値A[i],A[j],A[k]において、A[i] or (A[j] and A[k])の最大値を求めよ。

解法

最大値を上のビットから立てられるか判定していく。
今、ある値vを構築できるか判定していこう。

後ろの(A[j] and A[k])を処理するため、ある2進数の値xをビットマスクとして含むような値が2個以上存在するかどうかを数え上げていこう。
A[u]をuの大きい順に見ていき、A[u]の部分ビットマスクに相当する値の登場回数を数えていけばよい。
途中で2回以上登場した値に関しては、その値に含まれる値は処理を省略できる。

そしてA[i]に対し、A[i] or (A[j] and A[k]) = vを達成できるかどうかは、(A[i]^v)を含む値が2回以上登場しているかどうかで見ればよい。

int N;
int A[2020202];
int num[1<<21];

int ok(int mask) {
	int i;
	for(i=N-1;i>=0;i--) {
		int cm=mask&A[i];
		int lef=mask^cm;
		if(num[lef]>=2) return 1;
		if(num[cm]>=2) continue;
		num[cm]++;
		vector<int> V;
		V.push_back(cm);
		int j;
		FOR(j,21) {
			vector<int> V2;
			FORR(v,V) if(v&(1<<j)) {
				int nv=(v^(1<<j));
				if(num[nv]<2) {
					num[nv]++;
					V2.push_back(nv);
				}
			}
			FORR(v,V2) V.push_back(v);
		}
		
	}
	return 0;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	
	FOR(i,N) scanf("%d",&A[i]);
	
	
	int ret=0;
	for(i=20;i>=0;i--) {
		ZERO(num);
		if(ok(ret|(1<<i))) ret|=1<<i;
	}
	cout<<ret<<endl;
	
}

まとめ

これはちゃんと思いつけて良かったね。