CSAcademy Round #17 : D. Largest And Subset

典型？
https://csacademy.com/contest/round-17/#task/largest-and-subset

問題

N個の非負整数が与えられる。
このうちK個を選んでそれらのbitwise-andを計算するとき、得られる最大値を求めよ。

解法

2進数表記で上の桁から順に1にできるかどうかを確認する。
今対象の整数集合をAとする(Aの初期値は入力の整数群)。

dを大きい順に以下の処理を行えばよい。

• Aのうち、d bit目が1となる値がK個以上ある
  • K要素を選んだ時、bitwise-andを取ったのちd bit目を1とすることが可能である。よってAにはd bit目が1のもののみを残す。また解のd bit目は1となる。
• Aのうち、d bit目が1となる値がK個ない
  • K要素を選んだ時、bitwise-andを取ったのちd bit目を1とすることは不可能である。解のd bit目は0とし、処理を続ける。

int N,K;
vector<int> A;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>x, A.push_back(x);
	
	for(i=29;i>=0;i--) {
		vector<int> X;
		FORR(r,A) {
			if(r&(1<<i)) {
				X.push_back(r);
				r ^= 1<<i;
			}
		}
		
		if(X.size()>=K) A=X;
	}
	
	cout<<A[0]<<endl;
	
}

まとめ

これはすぐ思いついたし、Cよりもみな速く解いていた。