Codeforces #618 Div1 A. Anu Has a Function

まぁまぁ調子のよかった回。
https://codeforces.com/contest/1299/problem/A

問題

関数f(x,y)=(x|y)-yを考える。
N要素の整数列Aに対し、f(f(f(A[0],A[1]),A[2]),A[3])...と先頭2要素にfを適用して置き換える、という処理を繰り返すことを考えよう。

整数列Bが与えられる。Bを並べ替えて数列Aを作ったとき、上記手順で最後に残る値が最大となるような列を構成せよ。

解法

f(x,y)が行う処理は、xのうちyに含まれるbitを落とすことである。
ということは、上記処理は、A[0]の各bitにおいて、A[1]～A[N-1]のいずれかにそのbitが立っていたらそのbitを落とすことに相当する。

そこでBのうち各bitが立っている要素数を数えておいたうえで、A[0]となる値を総当たりし、上記処理の結果を求めて行けばよい。

int N;
int A[101010];
int D[32];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		FOR(j,30) if(A[i]&(1<<j)) D[j]++;
	}
	
	int ma=0,ret=0;
	FOR(i,N) {
		int mask=0;
		FOR(j,30) {
			if((A[i]&(1<<j)) && D[j]==1) mask|=1<<j;
		}
		if(mask>ma) {
			ma=mask;
			ret=i;
		}
	}
	cout<<A[ret];
	FOR(i,N) if(i!=ret) cout<<" "<<A[i];
	cout<<endl;
	
	
	
}

まとめ

まだ簡単だね。