【Python】ビット演算で全探索

はじめに

この記事は初心者競プロerが書いています。
もし間違っている所があれば、編集リクエスト又はコメントをお願いします。

想定読者

• ビット演算の雰囲気は分かるが、実装が分からい人

前提条件

• 論理積が何か分かる
• 10進数から2進数への変換が出来る

ビット全探索とは

bit 全探索とは、n個の要素からなる集合 {0,1,・・・・,n-1} の部分集合をすべて調べ上げる手法のことです。

000(0)~111(8)を表示していきます。

sample.py

#出力する値を入れる
ans = []

#左に3ビットシフト
for i in range(1 << 3):
    tmp = ""
    for j in range(3):
        # j番目が1か判定する
        if i & (1 << j):
            tmp += "1"
        else:
            tmp += "0"
    ans.append(tmp)
print(ans)


>>> ['000', '100', '010', '110', '001', '101', '011', '111']

これだけだとイマイチピンとこないので、Atcoderの問題を例に使い方を見ていきましょう。

A - 高橋君とお肉（ABC029）

こちらの問題を使用します。

考察

肉をどちらの機械で焼くのかを全て試します。
どういうパターンがあるのかを確認しましょう。

上の数字が肉の番号です。
〇が肉機器1で焼く、×が肉機器2で焼くことを表しています。
N=4の時は、全部で16パターン(2^4)あります。

実装

arc_a.py

n = int(input())
t = [int(input()) for _ in range(n)]

ans = []
for bit in range(1 << n):
    # 一つ目の肉焼き器
    x = 0
    # 二つ目の肉焼き器
    y = 0
    for i in range(n):
        #一つ目の肉焼き器で焼く
        if bit & (1 << i):
            x += t[i]
        #二つ目の肉焼き器で焼く
        else:
            y += t[i]
    ans.append(max(x, y))
print(min(ans))