E: Or Plus Max - AtCoder Regular Contest 100

K番目の解をanswer(K)と表すことにする。

$f(x) = max_{i \lor j = x}(A_{i}+A_{j})$ とおくと $answer(K) = max_{1 \leq x \leq K}f(x)$ が解。

f(x)の条件の部分をもう少し緩くしてみる。

$g(x) = max_{i \lor j \subseteq x}(A_{i}+A_{j})$ とおくと、後者の(i, j)の集合は、前者のそれを含むので $f(x) \leq g(x)$ が成り立つ。更に、 $i \lor j \neq x かつ i \lor j \subseteq x$ のとき $i \lor j \lt x$ が成り立つ。したがって以下が成り立つ。

$answer(K) = max_{1 \leq x \leq K} g(x)$

g(x)が簡単に求まるとしてanswer(K)は $answer(K) \gets max(g(K), answer(K-1))$

g(x)の求め方を考えてみよう。和を最大にするには、 $i \subseteq x$ であるようなA[i]について大きい方から2個を選んで使えばいい。そのためには、単にxの部分集合を列挙しながら2値を更新していく。部分集合の列挙は計算量3^Nなので間に合う。ただし、定数倍が厳しいので注意。2値の更新を雑に書いたらTLEした。あと出力が多いのでprintfを使ってもいいかも。

auto upd = [](pii &a, int x) {
    if (x > a.second) {
        a.second = x;
        if (a.first < a.second)swap(a.first, a.second);
    }
};

int N;
cin >> N;
int M = 1 << N;
vi A(M);
rep(i, M) cin >> A[i];
int re = 0;
FOR(S, 1, M) {
    pii ma(0, 0);
    int T = S;
    do {
        upd(ma, A[T]);
        T = (T - 1)&S;
    } while (S != T);
    smax(re, ma.first + ma.second);
    cout << re << endl;
}