天下一2017 - D - IntegerotS
概要
N個のふりかけが売られていて、それぞれのふりかけの番号はA[i]でおいしさがB[i]である。あなたはKという整数を持っている。次の条件を満たすようにふりかけを選んだ時のおいしさの和の最大値を求めよ。
K>=XのようなXがあり、えらばれたふりかけのすべてのA[i]のOR演算がXである。
制約： 1 <= N <= 10^5, 0 <= K, A[i] <= 2^30, 1 <= B[i] <= 2^30
ACするまで
1. (K|A[i])==Kのものは無条件に採用してよい。そうでないものについて考える。
2. OR演算でK以下なので、できるだけ多くのふりかけを選べるようにK以下で2進数で...111111と桁が立ってるものは、一番多く選べる可能性がある。(でもどこで111の境目を切るのか？)
3. 全部試せばOK->AC
考察
OR演算ということなので、「X or 候補 == X」ならば、Xに完全に含まれていることになって採用可能、そうでなければ採用不能である。
XはK以下なので、K以下でどのようなものがよさそうなのだろうか？
2進数表記で、
K=1101001 X=1100101 (x_0とする) X=1100100 (x_1とする) X=1100111 (x_2とする)
x_0, x_1, x_2のうち、x_2=Xであれば、ほかの2種をカバーできる。
このとき、Xはつぎのように構成されてる。
- 上から数桁はKと同じ(例の1~3桁)
- Kが1の桁でXは0と埋める。(例は4桁目)
- 残った下の桁たちを1で埋める。(例の5~7桁)
Kが1の桁でXを0で埋めることで、それより下の桁はどのように埋めても、必ずK未満となるのだ。(桁DPの未満フラグ的な)
このとき、下の桁たちで、1がたてばたつほど、より多くの候補を含めることから、全部1埋めすることで、ほかの候補をカバーできるということである。
このように考えたときに、実はXはO(K)だけ探索する必要はなくて、「Kが1の桁でXは0と埋める」候補を全部試せばいいとわかる。これはたかだかO(log K)である。
あとは、毎回Xを定めて、(X | 候補) == Xのような候補たちを合算して、最大値を毎回計算して更新すればよい。
計算量はO(N log K)
ACソースコード：
一言
今日はABCの日です。(2020/04/12)どこまで冷えますか？
