イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。

84. ビット全探索について丁寧に見る

プログラミング アルゴリズム

簡単な全探索を考える

唐突ですが、次のような問題を考えてみます。

【問題 A】
3 種類の硬貨 A, B, C が 1 枚ずつ存在します。
A, B, C の価値はそれぞれ 2, 3, 5 です。
これらの硬貨を組み合わせて、ぴったり支払える金額は何種類ありますか。
ただし、1 枚も選択しないパターンも含みます。

 

この問題は、それぞれの硬貨を「使う」「使わない」の 2 通りで全探索します。これは、以下のような 3 重ループで実現できます（C# で記述します）。

 

public void Solve()
{
    int A = 2;
    int B = 3;
    int C = 5;

    var set = new HashSet<int>(); // 重複のない集合
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            for (int k = 0; k < 2; k++)
            {
                int elem = 0;
                if (i == 1) elem += A;
                if (j == 1) elem += B;
                if (k == 1) elem += C;

                set.Add(elem);
            }
        }
    }

    var ans = set.Count;
    Console.WriteLine(ans); // 出力は 7 になる（支払える金額: 0, 2, 3, 5, 7, 8, 10）
}

 

種類数が増えると…？

先ほどは 3 種類だったので良かったですが、以下のような問題はどうでしょうか。

【問題 B】
10 種類の硬貨  C_i（ 1 \le i \le 10）が 1 枚ずつ存在します。
硬貨の価値は順に (2, 3, 5, 7, 11, 13, 17, 19, 23, 29) です。
これらの硬貨を組み合わせて、ぴったり支払える金額は何種類ありますか。
ただし、1枚も選択しないパターンも含みます。

 

もちろん 10 重ループを書いてもよいのですが、ちょっとつらいです。文字の書き間違いなどケアレスミスも怖いです。

ここで利用するのがビット全探索という手法です。【問題 B】は、以下のようなコードで解けます。

 

public void Solve()
{
    int N = 10;
    var v = new int[]
    {
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29
    };

    var set = new HashSet<int>(); // 重複のない集合
    for (int i = 0; i < (1 << N); i++)
    {
        int elem = 0;
        for (int j = 0; j < N; j++)
        {
            if (((1 << j) & i) > 0) elem += v[j];
        }
        set.Add(elem);
    }

    var ans = set.Count;
    Console.WriteLine(ans);
}

 

このコードは、初めて見たときはなかなかギョッとすると思います。一見何をしているのか分からないのですが、この記述は最適化を重ねた結果です。

主要部分のみを抜粋し、もう少し理解しやすい形に書き直したものが以下になります。

 

    int P = (int)Math.Pow(2, N);
    for (int i = 0; i < P; i++)
    {
        int elem = 0;
        for (int j = 0; j < N; j++)
        {
            int flag = (int)Math.Pow(2, j);
            if ((flag & i) > 0) elem += v[j];
        }
        set.Add(elem);
    }

 

順に見ていきましょう。最初の P ですが、各硬貨は「使う」「使わない」の 2 通りで、それが N (=10) 種類存在します。よって、硬貨の選択パターンは 2^N 通りあります。i のループは、これを全探索しています。

次に、flag ですが、j を各硬貨に対応させて、j に合わせて 1 となるビット位置を調整しています。以下の図に、各数値とビット状態の例を示しています。

 

f:id:ibako_piyo:20220316224627p:plain
i=6, 0 \le j \le 3 における flag のビット状態

 

この状態で、i と flag の AND 演算を行います。この二項演算は、各ビットについて双方 1 である箇所のみ 1 にして、それ以外は 0 とするような演算です。つまり、今回の例では以下の図の緑で囲んだ部分のみ 1 となります。

f:id:ibako_piyo:20220316225328p:plain
(i & flag) の演算結果（赤色セルのみ 1 になる）

 

よって、i = 6 のときは、j = 1, 2 のときのみ、このビット演算は 0 より大きくなります。これは、j = 1, 2 と対応した硬貨のみを使う、ということを意味しています。

ある数のビット状態は、その数を 2 進数で表したものと言い換えることができます。 2^N 未満の全パターンを列挙するため、これで全探索が可能になります。

 

ビット演算による最適化

以上の処理を最適化したものが、最初に示したコードです。順番に見ていきます。

まず、P の演算（ 2^N）で「(1 << N)」という記述をしています。これはシフト演算で、1 を左に N 回シフトさせています。つまり、「0000 0000 0001」のようなビット状態を、「0100 0000 0000」にしています。これは 2 のべき乗計算と全く等しく、ビット演算に置き換えることでより高速になっています。

flag の演算も、同じように考えられます。

 

ビット演算は記述がやや特殊で読みづらくなるのは確かです。そのため、ビット全探索の考え方に慣れるまでは、通常の演算で表現しても良いと思います。そもそも AtCoder などの競技プログラミングではアルゴリズムの計算量が問われており、このような細かな（定数倍の）最適化を詰めるのは後回しでよいです。

 

ビット全探索を使う問題

atcoder.jp