蟻本と下記の記事を読んでいて、最初の全探索の記事でbit全探索について学習しました。その上で、次回以降どういう問題の時bit全探索が使用できるのか、どのように実装すればよいのかをAtCoderの問題をベースに解説していきたいと思います。

bit全探索の詳細などは別サイトのリンクを張っておきますので、そちらをご確認ください。

はじめに

ここでは、記事のメインコンテンツに入る前に、必要な情報をまとめておきます。

参考になるリンク集

bit演算について理解したいときは、こちらの記事を御覧ください。 qiita.com

bit全探索で問題を解く時の考え方

bit全探索で問題を解く時、基本となる性質を覚えておくと良いと思います

bit全探索はbit演算をフラグ管理に使用

bit全探索はbitをフラグ管理として使用します。例えばですが、Qiitaのリンクにもある部分和問題の例で考えてみます。

n 個の整数 a[0],a[1],…,a[n−1]a[0],a[1],…,a[n−1] が与えられる。これらの整数から何個かの整数を選んで総和を K とすることができるかどうかを判定せよ。

このn個の整数は、"選択された" or "選択されていない"という2つの状態で管理することができます。

a[0],a[1],…,a[n−1]a[0],a[1],…,a[n−1]

の状態を2進数で表すと

0101....0 (0: 選択されていない、1: 選択していない)

このような感じになります。2ⁿ通りあるので、全探索でも2ⁿ通り調べます。

これは、”n個の要素の部分集合に対する全探索”と言い換えることができます。

bit演算の各記述の意味

他に、bit演算での記述が意味することをまとめます

1. 1 << n は 2ⁿ を意味する
2. (各部分集合) & (1 << i) (i = 0,1,2...,n-1) は各bitが1かどうかを調べている

主に、この2つを覚えておけば実装するうえでそんなに問題ないかと思います

AtCoderの問題を使用した回答例

まず、AtCoderの問題を例として見ていきましょう。

問題へのリンク

atcoder.jp

考え方

まず、問題についてまとめてみましょう

問題概要

肉はN個ある(1 <= N <= 4)
i番目の肉を焼くのにかかる時間はtiかかる
肉を焼くプレートは2つあり、最大で2個並行で焼くことができる
すべての肉を焼くのにかかる最小の時間を求める

解法概要

まず、大前提として今回はbit全探索を使います。なぜbit全探索でとけるのかというと、各肉(i = 1-4)をどちらのプレートで焼くのか集合で表すことができるので、肉の部分集合の全体に対して、全探索を行うことで答えが導き出せるためです。肉の数も最大で4個なので、計算量も2⁴で済みます。

解法詳細

まず、各肉がどちらで焼けるのか2進数でフラグ管理をすると、下記のようになります。

肉 1 2 3 4
(0 : 肉焼き器1でやく、1 : 肉焼き器2で焼く)
0000
0001
0010
0011
....
1111

この各パターンに対して、肉焼き器1でかかる合計の時間と肉焼き器2でかかる合計の時間を計算して、大きい方を選択します。これをTとします。

そして、すべてのパターンでTを計算して、最小となるTが答えです。

実装

実装のリンクを張ります。 github.com

ポイントになるのはこの実装かなと思います。　

for (int bit = 0; bit < (1 << N); bit++)
{
    int total = 0;
    int t1 = 0;
    int t2 = 0;
    for (int i = 0; i < N; i++)
    {
        if ((bit & (1 << i)) > 0)
        {
            t1 += t[i];
        }
        else
        {
            t2 += t[i];
        }
    }
    total = Math.Max(t1, t2);
    res = Math.Min(res, total);
}

このfor文の表現ですが、bit は先程2進数で列挙したすべてのパターンの十進数表記です。なので、(1 << N)、つまり2^N(Nは標準入力で与えられる)まで調べます。

for (int bit = 0; bit < (1 << N); bit++)

次に、こちらです。これは具体的に見ていきましょう。

for (int i = 0; i < N; i++)
{
    if ((bit & (1 << i)) 
    { 略 }
    else
    { 略 }
}

まず、bit = 3 とします。つまり、2進数表記では bit = 0011 となります。

では、2つ目のforが何を示しているのかというと、0011の桁数分繰り返しています。つまり、i=0の時は0011 の一桁目の 1 になります。では、続きを見ていきましょう。

このような記述があります。これは 0011 と 2ⁱ のANDを計算しています。今回、i = 0 とした時、0011 & 0001 と考えられます。

if ((bit & (1 << i))

では、i =1 ,2 ,3 の時はどうなるかというと、

0010
0100
1000

と0011のANDを計算するのと同じです。つまり、各桁のフラグが立っているか(1であるかどうか)を調べています。あとは、いい感じに計算の処理を書けばOKです。

この問題は肉の最大数が小さいのでbit全探索ができましたが、10⁸ 以下になるようなNの数じゃないとおそらくTLEすることになると思います。なので、計算量のことも忘れないようにしましょう。

結論

全部分集合に対する全探索の時に使用
全パターンと各bitに対するfor文を使用
各bitが1かどうかしらべて、あとはいい感じに問題に沿った処理を実装

こんなところかなと思います。便利に感じますが、計算量だけは気をつけたいなと思います。

たくあんポリポリ

勉強したことを載せていきます。最近、技術系の記事はZennに書いています。(https://zenn.dev/chittai)

【AtCoder】【C#】bit全探索を用いてAtCoderの問題を解く時の考え方