Mister雑記

競プロやります。

ARC100-E 「Or Plus Max」 (700)

atcoder.jp

問題

長さ 2^Nの数列 (A_i) (0-indexed)が与えられる。

 1 \leq k \lt 2^Nなる各整数 kに対し、 \max \{ A_i + A_j \mid i \neq j, \; i \lor j \leq k \}を求めよ。ここで \lorはbitwise orを意味する。

制約

  •  1 \leq N \leq 18
  •  1 \leq A_i \leq 10^9

考察

以降、 j \subseteq i \iff i \land j = j ( \landはbitwise and)という記法を用いる。これは整数を「立っているbitからなる集合」と見たときに、集合における意味と一致する。また同様の理屈で、 |i|を立っているbitの数とする(絶対値ではない)。


 \max \{ A_i + A_j \mid i \lor j \lt k \}は既に求まっているので、代わりに \max \{ A_i + A_j \mid i \lor j = k \}を求めればよい。  i \lor j = kのとき i, j \subseteq kなので、「 i \subseteq kなる iを全列挙して上から2つを取る」という解法が考えられる。しかしこの計算量は O(2^{|k|})となるので遅すぎる。そこでこれを以下のような手法で高速化する1


例えばもっと簡単な問題として、各 kについて X_k = \max \{ A_i \mid i \subseteq k \}を求めたいとする。このとき、 X_kは以下の式で効率的に求められる。

 \displaystyle X_k = \max(A_k, \max \{ X_l \mid l \subset k, \; |l| = |k| - 1 \})

つまりそれまでの結果を使うことで、 kからbitを1つ下ろしたものだけを列挙すれば十分となる。この工夫によって、計算量は愚直な場合の O(2^{|k|})から O(|k|)に落ちる。


この手法を今回の問題に適用する。今回は大きい方から2つの要素が欲しいので、各 kについて「 i \subseteq kなる iで、 A_iが大きい方から2つ」という集合 Y_kを求めることにする。

ここで X_kでは最大値自体を持っていたのに対して、 Y_kは最大値を取るindexを持っていることに注意。これは A_i = A_jかつ Y_k = \{ i, j \}となるような場合があるためである。

このとき Y_kは、集合

 \displaystyle k \cup \bigcup_{l \subseteq k, |l| = |k| - 1} Y_l

から2つを取ることで求められる。この集合のサイズは O(N)なので、全体の計算量は O(N 2^N)となる。実装時は要素の重複を消し忘れないように注意。

実装例

atcoder.jp

int main() {
    Int n;
    std::cin >> n;
    Int m = (1 << n);
 
    Vector<Int> a(m);
    for (auto& x : a) std::cin >> x;
 
    Vector<Vector<Int>> max(m);
    max[0] = {0};
    // kの部分bit全体で、aが大きい方から2つ(0だけ1つ)
 
    Int ans = 0;
    for (Int k = 1; k < m; ++k) {
        auto& idx = max[k];
        idx.push_back(k);
 
        // kからbitを1つだけ下ろしたlについて、max[l]をマージ
        for (Int i = 0; i < n; ++i) {
            if ((k >> i) & 1) {
                Int l = k - (1 << i);
                for (auto x : max[l]) {
                    idx.push_back(x);
                }
            }
        }
 
        // a[i]の大きさによってソート
        // 後でuniqueで重複を消すため、a[i]が同じ場合はiについてソート
        std::sort(idx.begin(), idx.end(), [&](Int i, Int j) {
            return (a[i] == a[j] ? i < j : a[i] > a[j]);
        });
 
        // 重複を消して大きい方から2つを残す
        idx.erase(std::unique(idx.begin(), idx.end()), idx.end());
        idx.resize(2);
 
        ans = std::max(ans, a[idx[0]] + a[idx[1]]);
        std::cout << ans << std::endl;
    }
    return 0;
}

補足

misteer.hatenablog.com


  1. この手法は高速ゼータ変換と似て非なるものである。高速ゼータ変換を使った解法は本記事末尾のリンクを参照。