ARC100 E問題 Or Plus Max - 輪郭をなぞるだけのブログ

問題概要

長さ $2^{N}$ の整数列 $A_{0}, A_{1}, ..., A_{2^{N} - 1}$ がある。
$1 \leq K \leq 2^{N} - 1$ を満たすすべての整数 $K$ に対して、次の問題を解く。

整数 $i, j$ に対して、 $0 \leq i < j \leq 2^{N} - 1$ , ( $i$ or $j$ ) $\leq K$ を満たす $A_{i} + A_{j}$ の最大値を求める。ただしここで or はビットごとの論理和を表す。

制約

$1 \leq N \leq 18$
$1 \leq A_{i} \leq 10^{9}$

考察 → 実装

ある $K$ を見ているとき、最大値に関わり得る要素の配列上の添え字は $K$ 以下である。
というのも論理和を取っているので、 $K$ より大きい添え字が関わると論理和が $K$ より大きくなってしまい、条件を満たさないからである。
$K$ 未満の最大値はすでに決まっているので、新しく最大値になり得るものとして、添え字の論理和が $K$ (以下)となるものを考える。
これは、 $K$ を 2 進表記で表したときの部分集合に属する添え字の要素を見ていけばよい。
例えば、 $K = 6\ (=110)$ のときは、部分集合は $\{000, 010, 100, 110\}$ となるので、見るべき添え字は $\{0, 2, 4, 6\}$ となる。
これらの要素で最大値と 2 番目に大きい値との和と、 $K$ 未満での最大値とを比較すれば、 $K$ での答えが求まる。

部分集合列挙であるが、ビット全探索のループの中でもう一度ビット全探索をやってしまうと、 $O(4^N)$ かかってしまう。
部分集合列挙を次のように高速化することで、部分集合列挙の計算量は、 $2^{popcount(S)}$ とすることができる。
ここで、 $popcount(S)$ は、ビット全探索中で今見ている数 $S$ を 2 進表記で表したときに立っているビットの個数のことである。

int S;  // 対象の集合
int subset = S;  // S の部分集合
while(subset){
    /* 部分集合に対する処理をここに書く */
    subset = (subset - 1) & S;  // 部分集合更新
}

読み飛ばしてしまっていたが、蟻本にも載っている。
部分集合列挙をこのように処理することで、ビット全探索の計算量は次のようになる。

$\displaystyle\sum_{S=0}^{2^{N}-1} 2^{popcount(S)}$

$= \begin{eqnarray*} && {}_N C _0\end{eqnarray*} 2^{0}$ $+$ $\begin{eqnarray*} && {}_N C_1\end{eqnarray*} 2^{1}$ $+ ... +$ $\begin{eqnarray*} && {}_N C _N\end{eqnarray*} 2^{N}$

$= \displaystyle\sum_{i=0}^{N} \begin{eqnarray*} && {}_N C _i\end{eqnarray*} 2^{i}$

$=(2 + 1)^N$

$= 3^{N}$

$O(3^N)$ だと通らないと思ったが、C++ だと 700ms 前後で通ってしまった。

コード

#include <iostream>
#include <vector>
using namespace std;

#define chmax(x, y) x = max(x, y)

int main(){
    int N;
    cin >> N;
    vector<int> A(1 << N);
    for(int i = 0; i < (1 << N); ++i)   cin >> A[i];
    
    int res = 0;
    for(int K = 1; K < (1 << N); ++K){
        int firstmax = max(A[K], A[0]), secondmax = min(A[K], A[0]);
        int subset = (K - 1) & K;
        while(subset){  // 部分集合列挙
            int hoge = A[subset];
            if(hoge > firstmax)     swap(hoge, firstmax);
            if(hoge > secondmax)    swap(hoge, secondmax);
            subset = (subset - 1) & K;
        }
        chmax(res, firstmax + secondmax);
        cout << res << "\n";
    }
}

想定解 (高速ゼータ変換)

この部分集合列挙の操作は $O(3^N)$ の bitDP などで重要になるが、今回の問題では高速ゼータ変換を用いれば、 $O(N\times 2^{N})$ まで高速化できる。
高速ゼータ変換では DP のように値を保存していくことで、 $O(N \times 2^N)$ にできる。
$O(3^N)$ の解き方では $K$ の部分集合を列挙していたが、ここでは部分集合から $K$ での最大値と 2 番目に大きい値を更新している感じだろうか。

高速ゼータ変換はまだよく分かっていない。
現時点では DP の一種という印象である。
ほぼ写経したのだが、よく分かっていない段階だと、DP テーブルを使い回さずに書いた方がよかったかもしれない。
理解が進めば書き足すかもしれないが、それは未来の自分に期待しておく。

コード

#include <iostream>
#include <vector>
using namespace std;

#define chmax(x, y) x = max(x, y)
using P = pair<int, int>;

P dp[300005];

// dp テーブルの更新
void update(P& a, P b){
    if(a.first < b.first){
        a.second = max(a.first, b.second);
        a.first = b.first;
    }
    else    chmax(a.second, b.first);
    return;
}

// 最大値になり得る値の取得
int get_value(P& a){
    return a.first + a.second;
}

int main(){
    int N;
    cin >> N;
    vector<int> A(1 << N);
    for(int i = 0; i < (1 << N); ++i){
        cin >> A[i];
        dp[i] = P(A[i], 0);
    }
    
    // 高速ゼータ変換
    for(int i = 0; i < N; ++i){
        for(int K = 0; K < (1 << N); ++K){
            if(K & (1 << i)){
                update(dp[K], dp[K ^ (1 << i)]);
            }    
        }
    }
    
    int res = 0;
    for(int K = 1; K < (1 << N); ++K){
        chmax(res, get_value(dp[K]));
        cout << res << "\n";
    }
}

参考文献

AtCoder ARC 100 E - Or Plus Max (黄色, 700 点) - けんちょんの競プロ精進記録
 高速ゼータ・メビウス変換 - Mister雑記
 bitによる部分集合の列挙と数学的理解 - Ark's Blog