アルゴリズム #1 bit全探索[python][AtCoder]

本記事について

競技プログラミングで使用するアルゴリズムをまとめます。シリーズ化する予定です。
言語はpythonです。今回はbit全探索についてまとめます。
誤り等ありましたら、ご指摘いただけたら幸いです。

bit全探索とは

N個の異なる要素をいくつか選択するというケースにおいて、全パターン($2^N$個）を検証すること。

例1

問

商品A,Bがある。それぞれを購入する/しないの選択をした場合の全パターンを列挙せよ。

回答

パターンは以下の４($=2^2$)通り存在する。

1. 商品を一つも買わない。
2. 商品Aのみ購入
3. 商品Bのみ購入
4. 商品A,Bを購入

コード

product_list = ["A", "B"]
N = len(product_list)

for i in range(1 << N):
    buy_list = []
    for j in range(N):
        if i >> j & 1:
            buy_list.append(product_list[j])
    print(buy_list)
"""
実行結果
[]
['A']
['B']
['A', 'B']
"""

例2

問

長さ3の文字列を0または1の文字で構成した場合の全パターンを列挙せよ。

回答

全8パターン存在する。(000,100,...,111)

コード

N = 3
for i in range(1 << N):
    s = ["0", "0", "0"]
    for j in range(N):
        if i >> j & 1:
            s[j] = "1"
    print("".join(s))
"""
実行結果
000
100
010
110
001
101
011
111
"""

当アルゴリズムが活用できる問題

本記事で取り扱ったアルゴリズムを活用できる問題を以下にまとめます。
問題、及び回答を随時更新していく予定です。

No.	問題（リンク)	回答例（リンク)
1	AtCoder 197_C :ORXOR	回答例 コード