Or Plus Max [AtCoder Regular Contest 100 E]

https://beta.atcoder.jp/contests/arc100/tasks/arc100_c

前提知識

• 高速ゼータ変換の形

考察過程

1. 全てのKについて答えさせるので、dpで一気に計算しそうな雰囲気がある
2. しかもbitなので、bitDP感がある
3. 「i or j≦K」という制約からゼータ変換を忖度する
4. 「dp[msk] := i or j ⊆ mskを満たすA[i]+A[j]の最大値」を作れば累積maxで答えを構築できることを見つける
5. これなら高速ゼータ変換の形で最大値2つを用意すればいける

解法

https://beta.atcoder.jp/contests/arc100/submissions/2798867

2つのDPを作って答えを求める。
　
「dp1[msk] := i ⊆ mskを満たすiの中でA[i]の上位2つのiを保持」
これを作っていこう。
高速ゼータ変換の要領で作っていけばいいので、dp1[msk]を作る場合はmskのビットが立っている所を1つだけ下ろしたmsk'のdp1[msk']だけを使って更新すれば十分。
　
「dp2[msk] := i or j ⊆ mskを満たすA[i]+A[j]の最大値」
これはdp2[msk] = A[dp1[msk].first] + A[dp1[msk].second]で更新するだけ。
あとは、dp2を小さい順から累積maxをすると
「dp2[msk] := i or j ≦ mskを満たすA[i] + A[j]の最大値」
に変化するので、これを答える。

int N, A[1<<18];
pair<int, int> dp1[1 << 18];
int dp2[1 << 18];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(msk, 0, 1 << N) cin >> A[msk];
 
    dp1[0] = { 0, 0 };
 
    rep(msk, 1, 1 << N) {
        vector<int> v;
        v.push_back(msk);
        rep(i, 0, N) if (msk & (1 << i)) {
            v.push_back(dp1[msk - (1 << i)].first);
            v.push_back(dp1[msk - (1 << i)].second);
        }
        sort(all(v));
        v.erase(unique(all(v)), v.end());
        sort(all(v), [&](int a, int b){ return A[a] > A[b]; });
        dp1[msk].first = v[0];
        dp1[msk].second = v[1];
    }
 
    rep(msk, 1, 1 << N) dp2[msk] = A[dp1[msk].first] + A[dp1[msk].second];
    rep(msk, 2, 1 << N) chmax(dp2[msk], dp2[msk - 1]);
 
    rep(msk, 1, 1 << N) printf("%d\n", dp2[msk]);
}