Codeforces 336C Vasily the Bear and Sequence

問題

n個の正の整数a[i]が与えられる。
a[i]から異なるk個を選びb[0], ..., b[k-1]とする。

b[0] & b[1] & ... & b[k-1]を割り切る2^vのうち、vの最大値を
bの美しさと呼ぶ。（&はビット演算のand）
ただし最大値が存在しないときは美しさは-1である。

美しさを最大にするようなbの選び方を求め、どれか一つ出力せよ。
それが複数あるときは、kが最大になるようなものをどれか一つ出力せよ。

制約条件

n≦10^5
a[i]≦10^9

方針

美しさをiであると決めうちすると、条件に適した選び方というのは、
i番目のビットが1であるa[j]を「全部」とってきて、それの&を取るしかない。

何故なら、i番目のビット以下はなるべく0になっているほうがいいので、なるべく多くの項を取ったほうがよくて、
かつ、問題ではkが最大になるようになので、個数の条件にも適するから。

取ってきたら、それらの&を実際にとって、本当に条件を満たしているかを見ればよい。

ソースコード

int n, a[100000];

int main(){
	cin >> n;
	rep(i, n) cin >> a[i];
	
	for(int v = 30; v >= 0; v--){
		unsigned int bit = ~0u;
		int cnt = 0;
		
		rep(i, n) if(a[i] & 1 << v) bit &= a[i], cnt++;
		if(bit != ~0u && bit != 0 && (bit & (1 << v) - 1) == 0){
			cout << cnt << endl;
			rep(i, n) if(a[i] & 1 << v) cout << a[i] << " ";
			cout << endl;
			return 0;
		}
	}
	assert(0);
	return 0;
}