ABC197_C
Table of Contents
AtCoder Beginner Contest 197 C
お題
数列を区分けして、reduce
reduce(or)の結果たちをさらにreduce(xor)したものの最小値
ポイント
Nが小さいので全探索で大丈夫。
functoolsにreduce関数があるのでこういうときは大活躍。
Goだと気持ちよくかけない。
最小値を求めるときは、ansにできるだけ大きい数を入れておいて、
ループで更新していくのがセオリーだけど、 今回はどこも分けなかった場合をansに入れて、 ループは、一箇所以上に仕切りを入れる方式にした
bit全探索を使って仕切りを入れることもできるけど、 pythonは順列組み合わせが標準で関数が用意されているのでそちらを採用。
- ループ1：仕切りを何個か(i)
- ループ2: i個の仕切りをどこに置くか(lはiterable)
あとは分けた部分で、orとxorを計算する。
整数が保証されているのでint.__or__, int.__xor__を使用しているけど、
operator.or_, operator.xorとかが汎用的
解答
from functools import reduce
from itertools import combinations as comb
def main():
N = int(input())
A = list(map(int, input().split()))
ans = reduce(int.__xor__, A)
for i in range(1, N):
for l in comb(list(range(1,N)), i):
current = 0
_or = []
for k in l:
_or.append(reduce(int.__or__, A[current:k]))
current = k
_or.append(reduce(int.__or__, A[current:]))
_ans = reduce(int.__xor__, _or)
ans = min(ans, _ans)
print(ans)
if __name__ == '__main__':
# test()
main()
