半分全列挙による全探索の高速化

2020年3月15日その他bit全探索,全探索,テーマ記事,競プロ,半分全列挙,テクニック

N 個の要素の組み合わせを計算する際、N/2 ずつの2グループに分けてそれぞれを全列挙し、組み合わせ方を高速に求めるという工夫を「半分全列挙」と言います。

選択した数列の合計値を半分全列挙で探索する場合(\(2^4\)ずつに分ける)

英語では Split and List とか Meet in the middle などと呼ばれることがあるそうです。

簡単な例とアイディアの紹介

正の数からなる要素数 \(N=40\) の数列が与えられ、この中からいくつか選んで合計値を計算します。合計値が S 以下となるような選び方での最大の合計値を求めてみましょう。

N が大きいと全探索できない

単純な全探索では間に合わない

普通に全探索しようとすると、それぞれ「選択する」と「選択しない」の2通りあるので、\(O(2^N)\) の計算量で全ての組み合わせを列挙することができます。

しかし、 \(N=40\) の場合は、\(2^{40} ≒ 10^{12}\) 程度の組み合わせがあるので現実的ではありません。

半分なら全列挙しても間に合う

仮に \(N\) が 20 だった場合は、\(2^{20} ≒ 10^{6}\) 程度の組み合わせなので十分間に合います。

ここが半分全列挙を利用する際の重要なポイントです。

半分ずつに分けて高速化する

N/2 ずつの 2 グループに分けて全列挙

半分なら全列挙しても間に合うので、\(N/2 =20\) ずつの 2 グループに分けることを考えます。

グループの中からいくつか選択して合計値を計算することを考えます。2つのグループがあるので、\(2^{20} ≒ 10^{6}\) 通りの組み合わせが 2 つできることになります。

この組み合わせの集合を \(A, B\) などとします。(要素数は \(10^6\) 程度です。)

2グループ同士を組み合わせる際に高速化

普通に \(A\) と \(B\) を組み合わせて合計値を計算しようとすると、 \(10^6 × 10^6 = 10^{12}\) となってやはり間に合いません。

しかし、問題の条件は合計値が S 以下となる最大の値を求めることです。

仮に \(A\) の要素 \(a\) を固定すれば、「\(S-a\) 以下の最大の要素を \(B\) から選ぶ」という話に変わり、この値は二分探索で高速に求めることができます。

\(A\) の要素を固定して全探索するのに \(O(2^{N/2})\) だけかかり、二分探索に \(O(\log (2^{N/2}) )\) だけかかるので、最終的な計算量は \(O(2^{N/2} N) \) になります。

具体例

上述の手順を具体例で見ておきましょう。以下のような状況で、合計値が S 以下となるような選び方での最大の合計値を求めます。

  • \(N = 8\)
  • 数列:\(\{31, 15, 11, 20, 13, 8, 5, 9\}\)
  • \(S = 62\)

半分に分けて全列挙

まず数列を以下の2つに分けます。

  • グループ1:\(\{31, 15, 11, 20\}\)
  • グループ2:\(\{13, 8, 5, 9\}\)

それぞれでの合計値を全列挙すると以下のとおりです。

  • A:\(\{0, 31, 15, 46, 11, 42, 26, 57, 20, 51, 35, 66, 31, 62, 46, 77 \}\)
  • B:\(\{0, 13, 8, 21, 5, 18, 13, 26, 9, 22, 17, 30, 14, 27, 22, 35 \}\)

片方を固定して二分探索

例えば、A の要素 31 に対して、\(S-31 = 31\) 以下の数の最大値を B の中から探すことを考えてみます。B をソートしておけば二分探索が利用できそうです。

  • B:\(\{0, 5, 8, 9, 13, 13, 14, 17, 18, 21, 22, 22, 26, 27, 30, 35\}\)

条件を満たす数に 30 がありました。よってこの時の最大値は 61 になります。

あとは全ての A の要素に対して同様のことを行い、最大値を探せば良いです。ここでは、A の要素に 62 、 B の要素に 0 があるので、最終的な答えは 62 になります。

C++ での実装例

二分探索で「\(S-a\) 以下の最大の要素を \(B\) から選ぶ」場合は、upper_bound(B.begin(), B.end(), S - a) - 1 で選ぶことができます。

しかし、\(S-a\) の値が B の最小の要素よりも小さい場合は、B.begin()-1 と同じになり危ないです。B には必ず 0 が含まれていることに注意して、\(S-a \geq 0\) かをチェックしておきましょう。

また、そもそも \(S-a \geq 0\) が成立しなければ、問題の条件が成立することもありません。

グループごとの全探索は、ビット全探索を用いています。

※ verify していないのでコードが間違っている可能性があります。

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int N, S;
    cin >> N >> S;
    vector<int> num(N);
    for (int i = 0; i < N; i++) {
        cin >> num.at(i);
    }

    // グループ1をビット全探索で全列挙 (前半の半分)
    vector<int> A;
    for (int bit = 0; bit < (1 << N / 2); bit++) {
        int sum = 0;
        for (int i = 0; i < (N / 2); i++) {
            int mask = 1 << i;
            if (bit & mask) {
                sum += num[i];
            }
        }
        A.push_back(sum);
    }

    // グループ2をビット全探索で全列挙 (後半の半分)
    vector<int> B;
    for (int bit = 0; bit < (1 << (N - N / 2)); bit++) {
        int sum = 0;
        for (int i = 0; i < (N - N / 2); i++) {
            int mask = 1 << i;
            if (bit & mask) {
                sum += num[N / 2 + i];
            }
        }
        B.push_back(sum);
    }

    sort(B.begin(), B.end());  // B をソート

    // A の要素を固定して二分探索
    int ans = 0;
    for (auto a : A) {
        if (S - a >= 0) {
            ans = max(ans, a + *(upper_bound(B.begin(), B.end(), S - a) - 1));
        }
    }

    cout << ans << endl;

    return 0;
}

一般化とまとめ

最終的に、半分全列挙のテクニックは以下の形になることが多いです。

  1. 半分のグループ A を全列挙
  2. もう半分のグループ B を全列挙
  3. Aの全ての要素について以下を行う
    1. A から選ぶ要素を1つに固定したとき、条件に合う要素をBから高速に探す

競技プログラミングで注意しておくポイントとしては、

  • 1グループあたり\(10^6 ≒ 2^{20}\) 前後の要素数であることが多い
  • 「3.」では 二分探索や map, set など利用して高速化することが多い

などがあるでしょう。

練習問題