[AtCoder] ABC 197 C – ORXOR

問題

方針

長さ \( N \) の数列から得られる長さ \( 1 \) 以上の連続した部分数列は、\( 2^{N-1} \) 通りあるので、ビット全探索します。イメージとして、分割される位置をビット列で表し、その値を更新していけば良いです。

また、論理和と排他的論理和の性質として、非負整数 \( x \) に対して、

\begin{eqnarray}
x \ \mathrm{OR} \ 0 &=& x\\
x \ \mathrm{XOR} \ 0 &=& x
\end{eqnarray}

であることを利用して初期値を決めています。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int A[20];

int func(int l, int r) {
    int ret = 0;
    for (int i = l; i < r; i++) {
        ret = ret | A[i];
    }
    return ret;
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int ans = INT32_MAX;
    for (int i = 0; i < (1<<(N - 1)); i++) {
        int tmp = 0;
        int l = 0;
        for (int j = 0; j < N - 1; j++) {
            if (i & (1<<j)) {
                tmp = tmp ^ func(l, j + 1);
                l = j + 1;
            }
        }
        tmp = tmp ^ func(l, N);
        ans = min(ans, tmp);
    }
    cout << ans << "\n";
    return 0;
}