Tenka1 Programmer Contest 2017 D - IntegerotS (500)

D - IntegerotS

概要

N項の整数列A, Bと整数Kが与えられる。数列Aiからいくつかの項を選び、それらの項すべてについてのbitwise orがK以下であるとき、対応するBiの和の最大値を求めよ。

制約

1 ≦ N ≦ 10^5
0 ≦ K < 2^30
0 ≦ Ai < 2^30
1 ≦ Bi ≦ 10^9

方針

Aiの全ての組み合わせについて試すことはできない。

重要な点として、Ai | Aj ≦ Ajであれば、Ajを選ぶときAiを一緒に選んでもbitwise orは変化しない。
ただし、解答を「Ai | K ≦ K なるiについてのBiの和」とするのは正しくない。
実際にA = {1, 2}, B = {100, 10}, K = 2のとき、上記は10となるが正解は100である。

視点を変えてみる。K' ≦ K なるK'について「Ai | K' ≦ K' なるiについてのBiの和」の最大値をとれば答えになる。
ここで探すべきK'を次のように絞ることができる。

• Kの上位i桁目のビットが1であるとき、K'の上位i-1桁目まではKと同じ、K'の上位i桁目は0、それ以下の位は1
• K'は、Kの上位i桁目のビットが1であるような全てのiについて上記の手順で得られる数とK自身に絞られる

計算量はKの1であるビットを選ぶのがlog K、 Ai | K' ≦ K'の判定がlog K、Biの和をとるのがNであるためO(N * (log K)^2)で間に合う。

解答

Submission #6336945 - Tenka1 Programmer Contest

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int bit(int x, int n){
	return (x >> n) & 1;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, K;
	cin >> N >> K;
 
	vector<int> A(N);
	vector<ll> B(N);
	rep(i, N) cin >> A[i] >> B[i];
 
	int l = 32 - __builtin_clz(K);
 
	ll ans = 0;
	for(int i = 0; i < l; i++){
		if(bit(K, i) == 0) continue;
 
		ll tmp = 0;
		for(int j = 0; j < N; j++){
			int x = A[j];
			if(bit(x, i) == 1) continue;
 
			bool ok = true;
			for(int k = 30; k > i; k--){
				if(bit(x, k) > bit(K, k)) {
					ok = false;
					break;
				}
			}
 
			if(ok) tmp += B[j];
		}
 
		ans = max(ans, tmp);
	}
 
	ll tmp2 = 0;
	for(int j = 0; j < N; j++){
		if((A[j] | K) <= K) tmp2 += B[j];
	}
 
	ans = max(ans, tmp2);
 
	cout << ans << endl;
}