【AtCoder】Pythonでビット探索

はじめに

ビット探索について、どんなものなのか、AtCoderなどではどんな問題で使うのか、Pythonで実装するためのサンプルコードについて紹介していきます。

実際のAtCoderで利用したプログラムも掲載しています。

ビット探索とは

ビット探索は、n個のものに対して選ぶ/選ばないやon/offなどの2通りがあるような場合に、全通りである\(2^n\)通りを探索することです。

下記の画像の場合は\(n=5\)になるので、全部で32通りになります。

それぞれ2通りあるので、選ぶ/選ばないを0と1で表し、全体を2進数で表すことができます。

実装する場合には、0から\(2^n-1\)までの10進数を2進数で表し、各ビットの0/1で探索していきます。

使いどころ

AtCoderなどでは以下の状況でビット探索が有効です。

  • 選ぶ/選ばないやスイッチのon/offなどそれぞれの候補に対して2通りのパターンがある
  • 全体の数であるNがそれほど大きくない

ビット探索のサンプルコード

ビット探索の基本となるサンプルコードです。

前提として、ビット単位演算とシフト演算の知識が必要になります。ビット単位演算とシフト演算については下記で説明しています。

Pythonでビット単位演算とシフト演算
AtCoderでよく使うような2進数を使った演算をまとめています。2進数の表し方まずはPythonでの2進数の基本的な扱いを理解します。2進数に変換するにはbinを利用します。>>> x = 13>>> y...
n = 3

patterns = []
# 0~2^n-1をループして2^n通りを試す
for i in range(2**n):  # 1<<nとしているプログラムもある
    p = [0] * n
    for j in range(n):
        # 0からn-1までjで右シフトして1とのANDをとることでビットが立っているか(1かどうか)判定
        if i >> j & 1: # if i & (1 << j): # これでも可
            p[j] = 1
    patterns.append(p)

print(patterns)

実行すると全てのパターンが列挙されていることがわかります。

[[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0],
 [0, 0, 1], [1, 0, 1], [0, 1, 1], [1, 1, 1]]

一番わかりにくいのは下記のコードかと思います。(私はそうでした)

if i >> j & 1:

簡単に言えば\(i\)を2進数と考えた時、下から\(j\)桁目が1になっているかを判定しています。

サンプルコードの全体から考えると、探索の全パターンとなる\(i(0 \leq i \leq 2^n)\)を\(j\)で0から\(n-1\)まで桁をずらしながらビットが立っているか(1になっているか)を判定していることになります。

AtCoderのサンプル問題

ABC128 C問題

C - Switches
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

スイッチのon/offのパターンを列挙して、条件を満たす組み合わせを求める問題です。

ビット探索でパターンを求めてから、条件に当てはまるか判定しています。

n, m = map(int, input().split())
k = []
s = []
for _ in range(m):
    tmp = list(map(int, input().split()))
    k.append(tmp[0])
    s.append(tmp[1:])
p = list(map(int, input().split()))

ans = 0
for i in range(2**n):
    switch = [0] * n
    # スイッチのon/offのパターンをビット探索で
    for j in range(n):
        if(i >> j) & 1:
            switch[j] = 1

    # 全ての電球が点灯するか
    check = True
    for j in range(m):
        k_sum = 0
        for s_i in range(k[j]):
            k_sum += switch[s[j][s_i]-1]
        if k_sum % 2 != p[j]:
            check = False
            break
    if check:
        ans += 1

print(ans)

ABC147 C問題

C - HonestOrUnkind2
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

「正直者」と「不親切な人」のパターンをビット探索で列挙して、それぞれの証言と矛盾していないか判定しています。

n = int(input())
A = []
X = []
Y = []
for _ in range(n):
    a = int(input())
    A.append(a)
    x = []
    y = []
    for _ in range(a):
        _x, _y = map(int, input().split())
        x.append(_x-1)
        y.append(_y)
    X.append(x)
    Y.append(y)

ans = 0
# ビット探索で正直者を仮定する
for i in range(2**n):
    check = True
    honest = []
    for j in range(n):
        # 正直者だけ矛盾してないか判定
        if (i >> j) & 1:
            honest.append(j)
            for k in range(A[j]):
                if Y[j][k] != ((i >> X[j][k]) & 1):
                    check = False
                    break

    if check:
        ans = max(ans, len(honest))

print(ans)

ABC197 C問題

C - ORXOR
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

数列の間に区切りを入れる/入れないでビット探索でパターンを列挙して、全通りを試して最小値を求めています。

n = int(input())
A = list(map(int, input().split()))

ans = 2**30

# 区切る箇所をビット探索で
for i in range(2**(n-1)):
    or_ = 0
    xor = 0
    for j in range(n):
        or_ |= A[j]
        # 区切る箇所がきたら
        if (i >> j) & 1:
            xor ^= or_
            or_ = 0
    xor ^= or_
    ans = min(ans, xor)

print(ans)

参考

タイトルとURLをコピーしました