AtCoder-ABC197 C - ORXOR【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210328211923p:plain
AtCoder Beginner Contest197のC - ORXORについてPythonの解答例を記事にしていきます。
atcoder.jp

AtCoder Beginner Contest197 C - ORXOR

問題文

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

制約

・1≤N≤20
・0≤Ai<2^30
・入力に含まれる値は全て整数である

解答例

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

# 解答ansはINFで初期化
INF = 1e9

ans = INF

# 数列が1つだけなら演算不可
if len(A) == 1:
    print(A[0])
else:
    # 区間の分け方をbit化
    for bit in range(2**(n-1)):
        # 区間内のbit単位or
        log_sum = A[0]
        # すべての値のbit単位xor
        xor = 0
        # 数列を探索
        for i in range(1,n):
            # bitが1なら区間終了
            if (bit >> (i-1)) & 1:
                # xorを計算
                xor ^= log_sum
                # orは0にしたあと数列A[i]とbit演算
                log_sum = 0
                log_sum |= A[i]
            else:
                # bitが0ならそのまま数列A[i]とbit演算
                log_sum |= A[i]

        # A[n]でループを抜けたらxorを計算
        xor ^= log_sum
        # 最小のxorをansに記録
        ans = min(ans,xor)

    print(ans)

解説

長さNの数列Aが与えられ、空でない任意の区間にわけます。
この区間内の数のビット単位orを計算し、求まったすべての値のビット単位xorの中で最小値を答える問題です。

数列の長さは20までなので、bit全探索を用いて区間の分け方を考えていきます。

入力例1を例にあげると、コードのbitが0のときは区間を分けずに[1,5,7]のビット単位orを求めます。
Pythonではビット演算子|（読み方がわかりません (^_^;)）を用いることでビット単位orが求まり、区間を分けないのでビット単位orがそのままビット単位xorです。
bitが1（2進数で01）のときは[1,5]と[7]に分け、区間のビット単位orを求めました。
xorはビット演算子^を用いて計算できますので、区間が終われば順次ビット単位xorを演算していきます。
bitが2（2進数で10）のときは[1]と[5,7]に分け、同様にビット単位xorを演算します。
bitが3（2進数で11）のときは[1]と[5]および[7]の3つの区間分け、xorを求めました。