World CodeSprint 11 : E. The Best Mask

またビット並列か。
https://www.hackerrank.com/contests/world-codesprint-11/challenges/best-mask

問題

N要素の整数列Aが与えられる。
以下を満たすXを答えよ。

• 全A[i]に対し、A[i] and Xは非ゼロ
• 上記を満たすXのうち、二進数表記で1の数が最少
• 上記を満たすXが複数ある場合、そのうち最少値

解法

A[i]は0≦A[i]≦(2^26)だが、A[i]=2^26の時は他のビットが立たないため、Xに2^26のビットを立てることとして以後無視しよう。

A[i] and Xが非ゼロということは、Xは~A[i]に含まれるbit列であってはならない。
よって、~A[i]に含まれるbit列を列挙すれば、最初の条件を満たすXが列挙できる。
あとはその中で後ろ2つの条件を見ればよい。

こうなるとbit列の部分列を求める問題になるので、高速ゼータ変換の要領で行える。
max(A[i])=2^Wと置くとO(W*2^W)かかり、愚直に行うとちょっと重い。
求めたいのは、最初の条件を満たすか満たさないかの真偽値なので、bit演算に落とし込んで無理やり対応しよう。

int N;
ll A[101010];
unsigned long long B[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int ret=0;
	cin>>N;
	FOR(i,N) {
		cin>>x;
		if(x==1<<26) {
			ret |= 1<<26;
			x ^= 1<<26;
		}
		x ^= (1<<26)-1;
		B[x>>6] |= 1ULL<<(x&63);
	}
	FOR(i,26) {
		if(i<6) {
			unsigned long long mask[6]={
				0xAAAAAAAAAAAAAAAAULL,
				0xCCCCCCCCCCCCCCCCULL,
				0xF0F0F0F0F0F0F0F0ULL,
				0xFF00FF00FF00FF00ULL,
				0xFFFF0000FFFF0000ULL,
				0xFFFFFFFF00000000ULL,
			};
			FOR(j,1<<20) B[j] |= (B[j]&mask[i])>>(1<<i);
		}
		else {
			FOR(j,1<<20) if((j&(1<<(i-6)))==0) B[j] |= B[j | (1<<(i-6))];
		}
	}
	
	int mi=(1<<26)-1;
	for(i=(1<<26)-1;i>=1;i--) if((B[i>>6]&(1LL<<(i&63)))==0 && __builtin_popcount(i)<=__builtin_popcount(mi)) mi=i;
	cout<<ret+mi<<endl;
	
	
}

まとめ

2^24位でもいい気がしたけどね。