bit全探索で解ける問題をPythonでひたすら解いていく

この記事ではタイトルにある通りbit全探索の問題をひたすら解いていきます。

bit全探索自体の解説は以下の記事を参照してください。
nashidos.hatenablog.com

例題1（難易度：茶）

atcoder.jp

問題文

高橋君は友達とキャンプに行くことになった。
高橋君と友達は性能が同じである 2個の肉焼き器を持っており、それぞれの肉焼き器にお肉を乗せて並行して焼くことができる。一旦肉焼き器にお肉を乗せたら、お肉が焼きあがるまではその肉焼き器からお肉を取り出したり、その肉焼き器に別のお肉を乗せたりはできない。お肉が焼けたらお肉を取り出すことができる。2 つの肉焼き器にまたがって 1 つのお肉を置くことはできない。また、お肉は全部で N 個あり、お肉には 1 から N まで番号が付けられている。お肉 を焼くのには、どちらの肉焼き器でも時間 だけかかる。お肉を肉焼き器に置く動作、取り出す動作には時間がかからない。
高橋君はお肉を焼く係であり、N個すべてのお肉を焼くことになった。みんなお腹が空いているので、すべてのお肉を焼くのにかかる時間を最小化させたい。
すべてのお肉を焼くのにかかる時間の最小値を求めよ。

制約
N(1≦N≦4)

実装

お肉の種類Nの制約が小さいことと、肉焼き器が２つであることから全部で通りであることがわかります。

なのでbit演算を利用してそのまま全探索するだけで答えが求まります。

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

ans = 10**9

for i in range(2**n):
    tmp = bin(i)[2:].zfill(n)
    a = []
    b = []
    for j in range(n):
        if tmp[j] == '0':
            a.append(t[j])
        else:
            b.append(t[j])
    ans = min(ans,max(sum(a),sum(b)))
print(ans)

例題2（難易度：茶）

atcoder.jp

問題文

on と off の状態を持つ N 個の スイッチと、M 個の電球があります。スイッチには 1 から N の、電球には 1 から Mの番号がついています。
電球 iは個のスイッチに繋がっており、スイッチ ,,...,のうち on になっているスイッチの個数を 2 で割った余りが に等しい時に点灯します。
全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。

制約
1≤N,M≤10
1≤≤N
1≤≤N

実装

この問題もNの制約が小さいことと「on」と「off」という２つの状態を持つことから全部で通りあることがわかります。

組み合わせの中から全ての電球が点灯するパターンを数えていくことで答えが求まります。

スイッチのon,offに関係のないスイッチがある場合に注意しましょう。

n,m = map(int,input().split())
switch = [(i+1) for i in range(n)]
ks = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
pattern = [bin(i)[2:].zfill(n) for i in range(2**n)]

ans = 0

for i in pattern:
    on = []
    light = 0
    for j in range(n):
        if i[j] == '1':
            on.append(switch[j])
    for k in range(m):
        count = 0
        for l in range(1,ks[k][0]+1):
            if ks[k][l] in on:
                count += 1
        if count % 2 == p[k]:
            light += 1
    if light == m:
        ans += 1
            
print(ans)

例題3（難易度：緑）

atcoder.jp

問題文

1 から N までの番号がついた N人の人がいます。彼らはみな、必ず正しい証言を行う「正直者」か、真偽不明の証言を行う「不親切な人」のいずれかです。
人 iは 個の証言を行っています。人 i の j 個目の証言は 2 つの整数 , で表され、 のときは「人 は正直者である」という証言であり、 =0 のときは「人 は不親切な人である」という証言です。
この N人の中には最大で何人の正直者が存在し得るでしょうか？

制約
1≤N≤15

実装

この問題もNの制約が小さいことと、N人の人を「正直者」か「不親切な人」か判断することから通りで全部調べることができることがわかります。

しかし、この問題は今までの問題のようにただbit全探索をすればいいわけではありません。

全パターンを探索したうえで、矛盾するパターンを取り除き、その中で正直者が最大数存在する答えを求める必要があります。

i番目の人が正しいと仮定すると、i番目の人の証言によってi+1番目の人は～みたいに考えると沼にハマります。

この問題は「不親切な人」「正直者」が0と1で表されているのでそのままbit全探索が使用できます。

n = int(input())
ls = []
for i in range(n):
    a = int(input())
    p = []
    for i in range(a):
        x,y = map(int,input().split())
        p.append([x-1,y])
    ls.append(p)

ans = 0

for i in range(2**n):
    flag = 0
    for j in range(n):
        if (i >> j)&1:#もし正直者だったら
            for k in ls[j]:#証言の確認
                if (i >> k[0])&1 != k[1]:#もし証言がおかしかったら
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans, bin(i)[2:].count('1'))#2進数表記の'1'の数が正直者の数
print(ans)

さいごに

この記事を参考にbit全探索の理解を深めてもらえたら嬉しいです。

今後もbit全探索で解ける良い問題を見つけたら順次追加していこうと思います。

おわり。