問題概要
問題ページ
-
-
https://atcoder.jp/contests/abc197/tasks/abc197_c
問題ページへ移動する
問題文
長さ \(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()