E - Or Plus Max AtCoder Regular Contest 100

問題概略

長さ2^Nの数列がある。
(i | j) <= K の時　Ai + A jの最大値を任意のKについて求めよ。

制約
N <= 18
Ai < 10^9

解法
i or j が K以下ということについて考える時、i or j が0の時、1の時、...Kの時という風に分けて考えたくなる。（使い回せるし）
i or j が K となるものを列挙するのは難しいが、今回知りたいのはK以下のものなので、i,jをKの部分集合とすれば良い。
よって部分集合をまとめ上げられる高速ゼータ変換を使う。

public static void solve() {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        int size = (1 << N);
        A = nia(size);
        P[] p = new P[size];
        for (int i = 0; i < size; i++) {
            p[i] = new P(A[i], 0);
        }
        //sの部分集合を総和する
        for (int i = 0; i < N; i++) {
            for (int s = 0; s < size; s++) {
                if (bitIsTrue(s, i)) {
                    merge(p[s], p[s ^ (1 << i)]);
                }
            }
        }
        for (int i = 1; i < size; i++) {
            chMax(p[i].x + p[i].y);
            System.out.println(maxRes);
        }
    }

    public static void merge(P p1, P p2) {
        int[] v = new int[4];
        v[0] = p1.x;
        v[1] = p1.y;
        v[2] = p2.x;
        v[3] = p2.y;
        revSort(v);
        p1.x = v[0];
        p1.y = v[1];
    }