PythonでOR演算、XOR演算を使った全探索を実装してみる-ABC197

この記事ではOR演算、XOR演算を用いた全探索をPythonで実装していきます。

一緒に例題を解きつつOR演算、XOR演算を使った全探索について理解しましょう。

OR演算、XOR演算の出力表

それぞれの演算子の入力されたビットに対する出力の表を以下に示します。

基本情報技術者試験などで最も最初に習う部分ですね。

入力1	入力2	論理和（OR）	排他的論理和（XOR）
1	1	1	0
1	0	1	1
0	1	1	1
0	0	0	0

OR演算

OR演算はPythonでは以下のように計算することができます。

print(2|5)
# 7

XOR演算

XOR演算はPythonでは以下のように計算することができます。

print(3^7)
# 4

例題

上記で触れたOR演算、XOR演算を踏まえ、今回は以下の問題を扱います。
atcoder.jp

問題文

長さ N の数列 A が与えられます。
この数列を、1 つ以上の空でない連続した区間に分けます。
その後、分けた各区間で、区間内の数のビット単位 OR を計算します。
こうして得られた全ての値のビット単位 XOR として考えられる最小値を求めてください。

制約

• 
• 
• 入力に含まれる値は全て整数

実装

OR演算、XOR演算を用いて全探索を実装することで解決することができる問題です。

区間の分け方を全通り試す方法が真っ先に思いつく解法だと思いますが、分け方のパターンを上手く全探索するのが難しい問題になっています。

このような全ての分け方のパターンを全探索する方法としてbit全探索という方法があります。

bit全探索の解説は別記事でしているので、今回は説明を省略します。
nashidos.hatenablog.com
nashidos.hatenablog.com

以下が私が実際に書いたコード例です。
（実際にAtCoderで提出する際はPyPy3で提出してください）

n = int(input())
a = list(map(int, input().split()))
pattern = [bin(i)[2:].zfill(n-1) for i in range(2**(n-1))] # 全てのパターンを列挙
ans = 10**10
if n == 1: # nが1の場合は問答無用で与えられた数字が答え
    print(a[0])
else:
    for i in range(len(pattern)):
        A = a[0]
        temp = []
        for j in range(len(pattern[i])):
            if pattern[i][j] == '1': # 1の場合に区切ることとする
                temp.append(A)
                A = a[j+1]
            else:
                A |= a[j+1] # OR演算
        temp.append(A)
        result = 0
        for k in temp:
            result ^= k # XOR演算
        ans = min(ans,result)
    print(ans)

まとめ

OR演算、XOR演算を用いて全探索を実装しました。

全探索は少し難しいbit全探索というアルゴリズムを用いました。

bit全探索、ビット単位OR, XOR演算などのビット系に慣れておくことで解ける問題の幅も増えるかもしれません。

おわり。