[Codeforces] Codeforces Round #687 (Div. 2) D. XOR-gun

2020年12月12日

問題

方針

排他的論理和の問題です。最上位のビットが同じ \( 1 \) である自然数を \( a_{i}, a_{i + 1}, a_{i + 2} \) とすると、

\[ a_i > a_{i +1} \oplus\ a_{i + 2} \]

となります。配列 \( a \) の連続する 長さ \( 3 \) の部分配列に着目したとき、その自然数の最上位のビットが同じ位置であるとき、上記の計算から答えは \( 1 \) となります。

ここで、部分配列の自然数の最上位のビットが異なるように自然数の選ぶことを考えます。制約から \( a_i \) は最大で \( 10^9 \) なので、最大で \( 30 \) ビットとなります。したがって、\( a_1 = 1\) とすると、以降の自然数は、最上位のビットが同じものを \( 2 \) つ選ぶことができるので、配列のサイズは最大でも \( 59 \) となります。したがって、配列のサイズが \( 60 \) 以上であれば答えは \( 1 \) となります。  配列のサイズが \( 59 \) 以下のものは全探索することが可能です。

\( f(l, r) \) を \( l \leq i \leq r \) を満たす配列 \( a \) の排他的論理和とします。

\[ f(l, r) = a_l \oplus a_{l + 1} \oplus \cdots \oplus a_{r} \]

\( f(l, m) > f(m + 1, r) \) を満たせばよく、排他的論理和を行った操作の回数は、\( m – l + r – (m + 1) = r – l – 1 \) となります。

コード

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

int b[100001]{};

int f(int l, int r) {
    return b[r] ^ b[l - 1];
}

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b[i + 1] = (b[i] ^ a[i]);
    }
    if (n >= 60) {
        cout << 1 << "\n";
        return 0;
    }
    int best = n;
    for (int l = 1; l < n; l++) {
        for (int m = l; m < n; m++) {
            for (int r = m + 1; r <= n; r++) {
                if (f(l, m) > f(m + 1, r)) {
                    best = min(best, m - l + r - (m + 1));
                }
            }
        }
    }
    if (best == n) {
        best = -1;
    }
    cout << best << "\n";
    return 0;
}