bit全探索

AtCoder ABC167のC問題でbit全探索が出たので、
記事を見ながら実装した記録。

port53.hatenablog.com

目次

• bit全探索とは
• ABC167 C問題

bit全探索とは

N個のものがあり、その中かからいくつか選ぶ。その時N個のものについて、
選ぶ・選ばないの2択の組み合わせ全パターンを出したい時に使う。
この「選ぶ・選ばない」について2進数のbitに見立てて考える。

ABC167 C問題では、参考書を買う・買わないの組み合わせを出すことになる。
ここで本がN=3冊(A, B, C)あったとすると、場合分けは以下の通り。

10進数	2進数	買う本(A, B, C)
0	000	買わない
1	001	C
2	010	B
3	011	B + C
4	100	A
5	101	A + C
6	110	A + B
7	111	A + B + C

上記パターンをもとに、ビットに1が立っているものについて何らかの処理をしたい。
2進数を右にN桁分シフトして、1と論理積をとり、 最下位の桁が1であるかどうかを確認することで、
ビットに1が立っていることをチェックできる。(一番右を0桁目として扱う)

書き方は以下の通り

for bit in range(2**n):
    for i in range(n):
        if ((bit >> i) & 1):
            # ここでビットが立ったものについて処理

qiita.com

C. Skill Up

問題文

参考書を買う・買わないの2択、すべての購入パターンがほしいのでbit全探索の出番。
理解度がx以上になるかどうか判定するだけでなく、そうなった時の価格の最小値を出すのが厄介。

ポイント(bit全探索以外)

• リストの全要素について条件判定をする時、組み込み関数all()が便利

note.nkmk.me

解説ACしたコード

1. どの参考書を買う・買わないでビットを立てる
2. 買う参考書について、各アルゴリズムの理解度上昇値を加算・本の価格を加算
3. 価格の最小値を答えとして持っておく(最小値が決まるまで全パターン列挙)

# coding:utf-8
# bit全探索
n, m, x = map(int, input().split())
book = [list(map(int, input().split())) for _ in range(n)]
ans = 12 * (10 ** 5) + 1

for bit in range(2 ** n):
    tmp_book = [0] * m
    price = 0
    for i in range(n):
        if ((bit >> i) & 1):
            price += book[i][0]
            for j in range(m):
                tmp_book[j] += book[i][j + 1]
    if all(item >= x for item in tmp_book):
        ans = min(price, ans)

if ans != 12 * (10 ** 5) + 1:
    print(ans)
else:
    print(-1)

参考になりそうな例題

atcoder.jp