kmjp's blog

競技プログラミング参加記です

Codeforces #195 Div2. C. Vasily the Bear and Sequence

CF195はDiv2 Onlyなので不参加。
http://codeforces.com/contest/336/problem/C

問題

数列Bの美しさとは、全要素のandをとったものが最大2の何乗で割り切れるかを指す。

数列Aが与えられたとき、美しさが最大となるようなsubsetを求めよ。

解法

美しさが2^vとなると仮定した場合、A中で2^vのbitが立っている要素だけをsubsetとして選択してv桁目以下を0にできれば、そのようなsubsetが作れる。
後はvが大きい順にsubsetが作れるか試せばよい。

int N;
vector<ll> A;

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty,aa[5];

	cin>>N;
	FOR(i,N) A.push_back(GETi());

	FOR(j,31) {
		x=1<<(30-j);
		y=0x7FFFFFFF;
		f=0;
		FOR(i,N) if(A[i]&x) y&=A[i],f++;
		if(y%x==0) {
			_P("%d\n",f);
			FOR(i,N) if(A[i]&x) _P("%d ",A[i]);
			_P("\n");
			return;
		}
	}
}

まとめ

まだ簡単だね。