【ABC197 C】「ORXOR」を解く【Python3】

コンテスト一覧へ

 

長さNの数列Aを、1つ以上の連続した区間に分け、与えられた計算をするとき、考えられる最小値を求める問題です。

(今回、「Python3」では時間が間に合わなかったので、「PyPy3」で提出しています)

提出
n = int(input())
a = list(map(int, input().split()))
xormi = 2000000000
for i in range(1<<(n-1)):
    xor = 0
    oor = 0
    for j in range(n):
        oor |= a[j]
        if i>>j & 1 or j==n-1:
            xor ^= oor
            oor = 0
    xormi = min(xormi, xor)
print(xormi)

1つ以上の空でない連続した区間に分ける、ということをまず考えます。

長さNの場合、考えられる分ける箇所は「N-1」となります。

すべての箇所で分ける場合と分けない場合を考えたとき、パターンは「2N-1」となります。

 

二択のものの全パターンを調べる方法として「bit全探索」があります。

区切りがある場合を「1」、区切りがない場合を「0」として、2進数の00000~11111までを調べれば、25パターンすべて探索したことになります。

「>>」はビットシフト演算子といい、2進数を指定の数だけ右にシフトします。

「<<」は同様に左にシフトします。

x = 13
print(bin(x))          # > 0b1101
print(x << 1)           # > 26
print(bin(x << 1))        # > 0b11010
print(x >> 1)                       # > 6
print(bin(x >> 1))                  # > 0b110

「0b」は2進数の先頭につく文字列です。

「&」は論理積といい、2つの数字の両方が1の場合のみ、1を返します。

x = 7
y = 19
print(bin(x),bin(y))                # > 0b111 0b10011
print(x & y)                        # > 8
print(bin(x & y))                   # > 0b1000

 

問題に戻ると、

 if i>>j & 1 or j==n-1:
    xor ^= oor
    oor = 0

という箇所で、i を j回シフトさせ、1との論理積が1のとき、または、j の値が n-1 である場合に、ビット単位 XOR 演算の処理をしています。

「xormi」に、より少ない値を入れておき、最後に出力します。

スポンサーリンク

【ABC197】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。