CSAcademy Round #53 : E. Maxor

こっちの方が普通に解けた。
https://csacademy.com/contest/round-53/task/maxor/

問題

N個の整数列A[i]が与えられる。
このうち２つを選びbitwise-orを取るとき、得られる最大値Mとそれを成す対の数を求めよ。

解法

A[i]に対し、残りの要素のうち~A[i]とのandが最大になるものを求めればよい。
これを高速ゼータ変換の要領で求めよう。

まず以下を求める。
B[i] := A[j]のうちiがA[j]の部分ビット列となるような要素数

次に以下を求める。
C[i] := iの部分ビット列jのうち、B[j]が正のものの最大値

ここまでわかると、Aから２つ要素を選ぶ際、1つA[i]を選んだ時もう一つ選ぶべきはC[A[i]]であることがわかる。
よって(i or C[A[i]])の最大値を総当たりで求めれば、まず最大値Mの方は求められる。

Mがわかれば、片方にA[i]を選んだ時にbitwise orがMになるにはもう一つにB[A[i]^M]個を選べばよい。

int N;
int C[1<<17];
int S[1<<17];
int P[1<<17];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		C[x]++;
		S[x]++;
	}
	
	for(i=16;i>=0;i--) {
		FOR(j,1<<17) if((j&(1<<i))==0) S[j] += S[j|(1<<i)];
	}
	FOR(j,1<<17) if(S[j]) P[j]=j;
	for(i=16;i>=0;i--) {
		FOR(j,1<<17) if((j&(1<<i))) P[j] = max(P[j],P[j^(1<<i)]);
	}
	
	int ma=0;
	FOR(i,1<<17) if(S[i]) ma=max(ma,i | P[i^((1<<17)-1)]);
	
	ll cnt=0;
	FOR(i,1<<17) if(C[i]) {
		if(i==ma) {
			cnt += 1LL*C[i]*(N-1);
		}
		else if((i|P[i^((1<<17)-1)])==ma) {
			cnt += 1LL*C[i]*S[P[i^((1<<17)-1)]];
		}
	}
	cout<<ma<<" "<<cnt/2<<" "<<endl;
}

まとめ

ちょっと手間取ったけどこれはなんとか。