ORXOR [AtCoder Beginner Contest 197（Sponsored by Panasonic） C]

https://atcoder.jp/contests/abc197/tasks/abc197_c

解説

https://atcoder.jp/contests/abc197/submissions/21324728

全探索できそうか？

まず、分割方法の全てを全探索して、その最小値が取れないかを考えてみる。
分割の方法は、分割する箇所が数列Aの要素間になるので、分割を行う部分がN-1通りあり、
それが分割するかしないかなので、全部で2^N-1通りとなる。
これはNの最大値が20なので、2¹⁹で524288なので、5*10⁵くらいで間に合う。10⁶くらいまでなら余裕。
こういった、2^?の全探索をするときに使うのがbit全探索である。

bit全探索

やり方はdrkenさんとか、ググったらたくさん出てくるので見てみてほしい。

各分け方について、与えられた操作をしていく。
自分の実装では、これまでのXOR和を変数tot, 現在の区間のOR和を変数curで管理していく。
先頭から順に確認していき、分割されてないならその要素はcurにORして、
分割されてるなら、curをtotにXOR和したあと、curを空にしてその要素をORする。
最後にcurをtotにXORし忘れないようにすること。

int N, A[20];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    
    if (N == 1) {
        cout << A[0] << endl;
        return;
    }

    int ans = inf;
    rep(msk, 0, 1 << (N - 1)) {
        int tot = 0;
        int cur = A[0];
        rep(i, 1, N) {
            if (msk & (1 << (i - 1))) {
                tot ^= cur;
                cur = 0;
            }
            cur |= A[i];
        }
        tot ^= cur;
        chmin(ans, tot);
    }
    cout << ans << endl;
}