Atcoder水色への精選 100 問　全探索：ビット全探索(Python)

AtCoder Python 競プロ精進 全探索 精選100問 bit全探索

水色になるための精選100問、
今回は10~14までの「全探索：ビット全探索」です

qiita.com


(※bit全探索を知らない方へ：bit全探索に関するpythonの詳しい解説は以下がおすすめです）
qiita.com



前回↓
工夫して通り数を減らす全列挙
algo-archit.hatenablog.com

目次



10　ALDS_5_A - 総当たり

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja

N個の数字からどれを選ぶのかをbit全探索します

ここで各bitごとに０か１かの２通りの可能性があることから
2^n通りの可能性を試せば大丈夫です
今回はmax_n = 20なので100万通り

1 << n と 2^nは同じ意味なことに注意です

pythonでの実装例

n = int(input())
a = list(map(int,input().split()))
pos = set()

# n桁分のbit探索
for i in range(1 << n):
    point = 0
    for j in range(n):
        # j個目の商品が含まれるか
        if (i >> j)&1:
            point += a[j]
    # 作ることができるものをsetに加えていく
    pos.add(point)

q = int(input())
m = list(map(int,input().split()))

for i in m:
    if i in pos:
        print("yes")
    else:
        print("no")



11　AtCoder Beginner Contest 128 C - Switches

問題文
atcoder.jp

問題文は少し難解ですが、N個のスイッチのうちONにするものをbit全探索していき、各パターンで電球は点灯するのかどうかを検証します

pythonでの実装例

n,m = map(int,input().split())
li = [list(map(int,input().split()))[1:] for _ in range(m)]
p = list(map(int,input().split()))
ans = 0

for i in range(1 << n):
    switch = set()
    # どのスイッチがONになっているか
    for j in range(n):
        if (i >> j)&1:
            switch.add(j+1)
    # 点灯条件を満たすか
    for k in range(m):
        point = 0
        for l in li[k]:
            if l in switch:
                point += 1
        if point%2 != p[k]:
            break
    else:
        ans += 1

print(ans)



12　AtCoder Beginner Contest 002 D - 派閥

問題文
atcoder.jp

派閥に含める人の選び方をbit全探索します
選ばれた人から２人を選ぶときに矛盾が生じないかを確認すれば大丈夫です

pythonでの実装例

from itertools import combinations

n,m = map(int,input().split())
rel = {}

# ハッシュテーブルで管理
for _ in range(m):
    x,y = map(int,input().split())
    rel[x,y] = True

max_num = 1 # 作成可能な派閥の最大人数

# どの人を派閥に加えるか
for i in range(1 << n):
    human = []
    for j in range(n):
        if (i >> j)&1:
            human.append(j+1)
    for k,l in combinations(human,2):
        if (k,l) not in rel:
            break
    else:
        max_num = max(max_num,len(human))

print(max_num)



13　JOI 2008 予選 5 - おせんべい

問題文
atcoder.jp

どの列のおせんべいを裏返すかをbit全探索します
裏返すときにはその列の要素全体に対して１とXORでかけ合わせます
( 0 XOR 1 = 1, 1 XOR 1 = 0　なので )

こういった行列全体への計算にはnumpyを使うと便利です

また裏返し処理が終わったあと、各列の裏返っているせんべいの枚数をカウントします（Aと仮定）
この際に、その列の裏返っている枚数がR-A枚未満だった場合は列をひっくり返すのが最適です

pythonでの実装例

import numpy as np

r,c = map(int,input().split())
senbei = [list(map(int,input().split())) for _ in range(r)]
senbei = np.array(senbei,dtype=np.int64)
senbei_max = 0 # せんべいの最大枚数

# どの列を裏返すかをbit全探索する
for i in range(1 << r):
    senbei_c = np.copy(senbei)
    for j in range(r):
        if (i >> j)&1:
            senbei_c[j] ^= 1 # ひっくり返す
    count = senbei_c.sum(axis=0) # 現在の状態の列の裏返っている個数
    senbei_num = np.maximum(count,r-count).sum()
    senbei_max = max(senbei_num,senbei_max)

print(senbei_max)



14　Square869120Contest #4 B - Buildings are Colorful!

問題文
atcoder.jp

どの建物をｋ個以上見えるようにしたいかをbit探索します
i番目の建物が見えてほしいとき、i-1番目までの最高高さがi番目の建物以上の場合i番目の建物の高さをmax(a[ : i ])+1にします

pythonでの実装例

n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 10**20

# どのビルを見るかをbit全探索
for i in range(1 << n):
    li = []
    for j in range(n):
        if (i >> j)&1:
            li.append(j)
    if len(li) < k:
        continue
    point = 0
    now = a[0]# 最大高さ
    for l in range(1,n):
        if l in li and a[l] <= now:
            point += now+1-a[l]
            now += 1
        # 最大高さ更新
        now = max(now,a[l])
    ans = min(ans,point)

print(ans)

次回↓
順列全探索(15~17まで)
algo-archit.hatenablog.com