LoginSignup
19
6

More than 1 year has passed since last update.

こわくないbit全探索3 基本編2: 2進法を使って実装してみよう!【競プロ解説】

Last updated at Posted at 2021-11-15

競技プログラミング(AtCoder)初心者が、最初に突き当たる壁になることが多いアルゴリズムのひとつに『bit全探索』があります。

この記事では、その『bit全探索』についてできる限り丁寧に解説をしていきます。

※この記事では、Python・C++を使った実装を解説しています。

記事リンク

1. 入門編 bit全探索ってなに? : bit全探索はどんなことをするアルゴリズムなのか解説します。 
2. 基本編1 簡単な例題でbit全探索をやってみよう! : 簡単な例題(部分和問題)で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう! : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう! : AtCoderのbit全探索を使う問題のヒントとコード(Python・C++)を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう! : 再帰関数を使ってbit全探索に似た問題を解きます。

質問先など

ご指摘・ご質問はツイッター・マシュマロ・Discordサーバーまでお気軽にどうぞ!

Twitter: u2dayo
マシュマロ: https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー(質問や記事の感想・リクエストなどどうぞ!) : https://discord.gg/jZ8pkPRRMT

よかったらLGTM拡散していただけると喜びます!

2進法や論理演算について

この章では 『$2$ 進法』『ビット演算』という概念が出てきますが、軽く説明するにとどめます。よくわからない部分があれば、アルゴ式のビット演算の問題や、ITパスポートの問題で勉強することをおすすめします。

2進法を使ってbit全探索してみよう

前章では、Pythonのproduct関数を使ってbit全探索を行いました。

実は、別の方法で『選ぶ』『選ばない』を表現して、bit全探索を実装することもできます。むしろ、Pythonのproduct関数のような便利な関数がない言語では、こちらの方法を使うのが普通です。

2進法を使ったbit全探索のメリット・デメリット

具体的な内容に入る前に、$2$ 進法を使うメリットとデメリットを解説します。

メリット
  • ほとんどの言語で使える方法である
  • PyPyの場合、こちらの方法のほうが高速(Pythonでは同程度)
  • この方法に慣れておくと、今後役に立つ(bitDPなど、$2$ 進法の01で集合を表す考えが必要になる問題があります)
デメリット
  • タイプ量が多くて面倒(スニペットにするといいかも?)
  • 使用する演算子(ビット演算子)の優先順位がわかりづらく、慣れないとミスをしがち(よくわからなかったらとりあえずカッコをつけておこう!)

10進法と2進法

わたしたちは普段、$0,1,2,3,4,5,6,7,8,9,10,11,12,\dots$ と、$0$ ~ $9$ の $10$種類の数字を使い、$10$ ごとに桁が繰り上がる『$10$ 進法』で数字を扱っています。

しかし、コンピュータは人間とは違い、$0$ と $1$ の $2$ 種類の数字だけが使われていて、$2$ ごとに桁が繰り上がる『2進法』で数字が扱われています。$2$ 進法で数字を $0$ から数えると、$0,1,10,11,100,101,110,111,1000,1001,1010,1011,1100$ です。

$10$ 進法と $2$ 進法で表された数字は、表現の仕方が違うだけで同じ数字で、相互に変換が可能です。例えば、$10$ 進法で $5$ は $2$ 進法だと $101$、$2$ 進法の $1000$ は $10$ 進法の $8$ と全く同じ数字です。

2進法の "1" を『選ぶ』"0" を『選ばない』と考えると、bit全探索に使える!

ここで、$2$ 進法の整数の $1$ を『選ぶ』、$0$ を『選ばない』とみなして、$2$ 進法で下から $i$ 桁目が $1$ なら $i$ 番目を『選ぶ』、$0$ なら『選ばない』とみなすことにして、bit全探索に使うアイデアが出てきます。

そして、コンピュータは整数を $2$ 進法で扱っていますから、ある整数を $2$ 進法であらわしたときの、下から $i$ 桁目が $1$ か $0$ か取り出す操作は簡単にできます。

X = 12  # 2進法表記では1100(2^3 + 2^2 = 8 + 4 = 12)
for i in range(4):
    if X & (1 << i):  # X を2進法表記したとき下からi桁目が1か判定
        print(f"下から{i}桁目: 1")
    else:
        print(f"下から{i}桁目: 0")

このコードを実行すると下の出力が得られ、たしかに $i$ 桁目が $1$ か $0$ か判定できています。

下から0桁目: 0
下から1桁目: 0
下から2桁目: 1
下から3桁目: 1

なお、&論理積演算子)や、<<左シフト演算子)などを使って行う演算を総称して『ビット(bit)演算』と呼びます。整数を $2$ 進法とみなしたときの、$1$ と $0$ の列をビット列と呼び、ビット列に対する操作を行う演算のことを総称して『ビット演算』と呼ぶからです。

これが、『bit全探索』という名前の由来になっています。この他にもビット演算子はいくつかありますが、今回の記事では使わないので省略します。

実装

組み合わせを全列挙する部分

ans = 0
# 2進法表記で0 ~ 11...11(1がN桁)の整数をループ
# こう書いても、bitはただの整数ですから、print(bit)をすると10進法表記の3や5などが出力されます
# なお、range(1 << N) は range(2 ** N)と同じです
for bit in range(1 << N):  
    ans += judge(bit)
print(ans)

判定部分

def judge(bit):
    S = 0
    for i in range(N):
        if bit & (1 << i):  #整数bitを2進法とみなしたときの、下からi桁目が1か判定
            S += A[i]

    if S == W:  # S == W なら +1
        return 1
    else:
        return 0

全体

from itertools import product  # import文は一番上にまとめておくほうが良いです


def judge(bit):
    S = 0
    for i in range(N):
        if bit & (1 << i):  #整数bitを2進法表記したときの、下からi桁目が1か判定
            S += A[i]

    if S == W:  # S == W なら +1
        return 1
    else:
        return 0


N, W = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
# 2進法表記で0 ~ 11...11(1がN桁)の整数をループ
# このように書いても、bitは普通の整数ですから、printすると10進法表記の3や5などになります
# なお、range(1 << N) は range(2 ** N)と同じです
for bit in range(1 << N):
    ans += judge(bit)
print(ans)

C++の実装

Pythonと同じロジックですから、ほぼ同じようなコードになっています。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N, W;
    cin >> N >> W;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    int ans = 0;

    for (int bit = 0; bit < (1 << N); ++bit) {
        int S = 0;
        for (int i = 0; i < N; ++i) {
            if (bit & (1 << i)) {
                S += A[i];
            }
        }
        if (S == W) {
            ans++;
        }
    }

    cout << ans << endl;
}

おまけ: i桁目が1かどうかの判定の書き方

この記事では、bitを $2$ 進法で表したときの $i$ 桁目が $1$ か判定するために

bit & (1 << i)

と書きました。

他にも書き方があって、

bit >> i & 1

と書いても、bitを $2$ 進法で表したときの $i$ 桁目が $1$ かどうか判定することができます。

$i$ 桁目が $0$ のときはどちらも結果は $0$ ですが、$i$ 桁目が $1$ のときの結果が違います。

bit & (1 << i)1 << i($=2^i$)、bit >> i & 11 が返ります。

$i$ 桁目に $1$ が立っているか判定するときはどちらを使っても変わらないので好きなほうを使っていいですが、一応違いは覚えておきましょう。

記事リンク(再掲)

1. 入門編 bit全探索ってなに? : bit全探索はどんなことをするアルゴリズムなのか解説します。 
2. 基本編1 簡単な例題でbit全探索をやってみよう! : 簡単な例題(部分和問題)で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう! : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう! : AtCoderのbit全探索を使う問題のヒントとコード(Python・C++)を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう! : 再帰関数を使ってbit全探索に似た問題を解きます。

19
6
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
19
6