D - IntegerotS　Tenka1 Programmer Contest - バイトの競プロメモ

問題概略
N個の非負整数がああり、それぞれに価値がある。
いくつかをKを超えないようにorを取った時に価値を最大化したい。

制約
1≤N≤105
0≤K<230
0≤Ai<230(1≤i≤N)
1≤Bi≤109(1≤i≤N)
入力は全て整数である

解法
最初桁DPのようなことをやろうとした。oo桁目以降は自由に入れられる tightかどうかのように
しかし、条件が複雑すぎるので他の方法を考えた。
最終的な論理和について考えると、なるべくビットが立っていたほうがうれしい。
そのように考えると、上からあるビットまではKと一致しており、次の1のビットを0に、そしてそれ以降を1にしたものについて考えればいいとわかった。
どこまで一致させるかで30通りしかなく、最終的に内包される形が分かっていればその部分集合を足せば良い。
よって解けた

類題
D: 壊れた電卓 - CODE FESTIVAL 2014 予選A | AtCoder

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        long K = nl();
        A = niah(N, 2);
        B = niah(N, 2);
        int hib = highestOneBit(K);
        ArrayList<Long> kata = new ArrayList<>();
        kata.add(K);
        for (int i = hib; i >= 0; i--) {
            if (bget(K, i)) {
                long k = K ^ (1 << i);
                k |= (1 << i) - 1;
                //i桁目が1なら0にして、それ以下を1にする
                kata.add(k);
            }
        }
        for (Long k : kata) {
            long sum = 0;
            for (int i = 0; i < N; i++) {
                if ((k | A[i]) == k) {
                    sum += B[i];
                }
            }
            chMax(sum);
        }
        System.out.println(maxRes);
    }