ABC197 C問題 ORXOR をビット全探索で解く

ABC197のC問題 ORXORを解いてふりかえります。

atcoder.jp

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

長さNの数列のどこに区切りを入れるかで結果が変わってきます。
Nは、区切りを入れられる位置はN - 1箇所、最大でもなのでビット全探索でいけると思いました。

ただここからが問題で、区切りを入れる位置が決まったとして、それをどうやって表現して計算するか、かなり悩んで時間を使ってしまいました。

結局は問題文に書いてある通り、どの順番でXORやORの演算をやっても結果は変わらないというところがヒントでした。

ビットに1が立たないところではORの演算をしていって、ビットに1が立ったところ、つまり区切りのところでXORの演算をしてORの演算の結果をリセットします。

最後にORの演算をしっぱなしにしないで、ちゃんとXORの演算をするところも、軽くつまづきました。

最後はXORとORの計算した結果で最小のものを変数に入れて、最後に出力すれば答えになります。

N = int(input())
a_arr = list(map(int, input().split()))
# 届かないくらい大きい数を初期値に入れる
ans = 2**30

# N-1箇所で区切りを入れるか入れないかで
# ビットを立てる
for bit in range(2**(N - 1)):
    h_or = a_arr[0]
    h_xor = 0
    for i in range(1, N):
        if bit & 1 << (i - 1):
            h_xor ^= h_or
            h_or = 0
        h_or |= a_arr[i]
    h_xor ^= h_or
    ans = min(ans, h_xor)
print(ans)

1ヶ月前の自分はビット全探索って発想ができなかったし、まともに書けなかったけど、すぐに思いつけるようになったのは前進かなと思います。
まだバグを埋め込んだりしてしまうので、実装に時間がかかるのが課題です。