天下一プロコン2017 D - 西瓜の備忘録

天下一プロコンは調子乗ってBeginnerじゃないほう参加したら見事に爆死しました

Cはともかく、Dは自力で解けなかったので解法をメモ

問題概要：N個の非負整数がある　それぞれの値と価値はAi,Biである

Aiの任意の組み合わせの論理和がK以下となるようにしたとき、最大の価値の総和を求めよ

制約：

1 ≤ N ≤ 10^5

0 ≤ K ≤ 2^30

0 ≤ Ai ≤ 2^30(1≤i≤N)

1 ≤ Bi ≤ 10^9(1≤i≤N)

まず制約からして全探索、BitDPは不可能

bitwise orの特徴は A∨B = A ⇔ AはBの立っているビット全て立っている

なのでK以下の値に対してAiが含まれるかどうかを判定して、含まれている場合価値の和を取ればよさそう

次にK以下の値の取り方を考える　

論理和は0→1はあっても1→0という値の変化はしないため、Kに立っていないビットを取るようなK'(<K)を取れば全ての値をカバーできるはず

K'の取り方はKの立っているビットを下から探して、そのビットを0にした後に以下の桁を全て1で埋めれば良い

この方法だと計算量はO(NlogK)　ただしK=0の場合があるので注意