Edit

【pythonでABC197を解説】C - ORXOR

問題概要

問題ページ

C - ORXOR
C - ORXOR

問題ページへ移動する

問題文

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

ビット単位 \(\mathrm{OR}\) 演算とは

整数 \(A, B\) のビット単位 \(\mathrm{OR}\)、\(A\ \mathrm{OR}\ B\) は以下のように定義されます。

  • \(A\ \mathrm{OR}\ B\) を二進表記した際の \(2^k\) (\(k \geq 0\)) の位の数は、\(A, B\) を二進表記した際の \(2^k\) の位の数のうち少なくとも片方が \(1\) であれば \(1\)、そうでなければ \(0\) である。

例えば、\(3\ \mathrm{OR}\ 5 = 7\) となります (二進表記すると: \(011\ \mathrm{OR}\ 101 = 111\))。
一般に \(k\) 個の整数 \(p_1, p_2, p_3, \dots, p_k\) のビット単位 \(\mathrm{OR}\) は \((\dots ((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\ \dots\ \mathrm{OR}\ p_k)\) と定義され、これは \(p_1, p_2, p_3, \dots p_k\) の順番によらないことが証明できます。

ビット単位 \(\mathrm{XOR}\) 演算とは

整数 \(A, B\) のビット単位 \(\mathrm{XOR}\) 、\(A\ \mathrm{XOR}\ B\) は、以下のように定義されます。

  • \(A\ \mathrm{XOR}\ B\) を二進表記した際の \(2^k\) (\(k \geq 0\)) の位の数は、\(A, B\) を二進表記した際の \(2^k\) の位の数のうち一方のみが \(1\) であれば \(1\)、そうでなければ \(0\) である。

例えば、\(3\ \mathrm{XOR}\ 5 = 6\) となります (二進表記すると: \(011\ \mathrm{XOR}\ 101 = 110\))。
一般に \(k\) 個以上の整数 \(p_1, p_2, p_3, \dots, p_k\) のビット単位 \(\mathrm{XOR}\) は \((\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k)\) と定義され、これは \(p_1, p_2, p_3, \dots p_k\) の順番によらないことが証明できます。

制約

  • \(1 \le N \le 20\)
  • \(0 \le A_i \lt 2^{30}\)
  • 入力に含まれる値は全て整数である

問題の考察

ACコード

import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    mn = 10 ** 20
    for v in itertools.product(range(2), repeat=n):
        t = a[0]
        ls = []
        for i in range(1, n):
            if v[i] != v[i-1]:
                ls.append(t)
                t = a[i]
            else:
                t |= a[i]
        ls.append(t)
        ans = 0
        for i in range(len(ls)):
            ans ^= ls[i]
        mn = min(mn, ans)
    print(mn)


if __name__ == '__main__':
    solve()

-Edit
-