こどふぉ特有の、ややギャグ要素ありの楽しい問題。結構好き。

問題へのリンク

問題概要

長さ $N$ の正の整数からなる広義単調増加な数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。以下の操作を何度か行うことで、広義単調増加ではない状態にしたい。

数列の隣接する 2 つの要素を選んで、それらの XOR 和をとった値で置き換える (数列の要素数は 1 減少する)

操作回数の最小値を求めよ。実現不可能な場合は -1 を出力せよ。

制約

$2 \le N \le 10^{5}$
$1 \le A_{1} \le A_{2} \le \dots \le A_{N} \le 10^{9}$

考えたこと

まず最初に、次のような $O(N^{3})$ 解法を思いついた。操作によって出来上がった数列において、隣接要素 $P, Q$ が $P \gt Q$ となったとする。このとき、もとの数列 $A$ の隣接する区間 $\lbrack a, b)$ , $\lbrack b, c)$ があって

$A$ の区間 $\lbrack a, b)$ の XOR 和が $P$
$A$ の区間 $\lbrack b, c)$ の XOR 和が $Q$

というふうになっているはずである。この状態を実現するための操作回数は $c - a - 2$ 回となる。

よって、 $a, b, c$ を全探索するという $O(N^{3})$ の解法が生えた。

実はほとんど 1 回や 2 回でできるのでは

ここから先がなかなかわからなかった。ちょっと例によって、「苦手な高速化」が要求されているかもしれないという悩みに取り憑かれたかもしれない。

さて、色々手を動かしてみると、なんと割と大体のケースで 1 回で実現できてしまうことがわかった。逆にできないケースを作ろうとすると、こんなケースになる (二進法で書いてる)。

この場合は、どうやっても後ろの方の「より上位の桁の 1」を相殺して消すことができないので不可能。

でもこのケースを考えたことでちょっとわかってきた。 $N$ 個の整数で不可能な場合を作ろうとすると、 $O(N)$ 桁くらい必要になるのではないかという直感が働いたのだ。

さらによく考えると、やはりほとんどのケースで 1 回で済むことがわかった。たとえば

0001001101
0001011011
0001101110

のように、「最上位の 1 の桁」が一致するものが三連続で続くと、後半 2 つの XOR 和をとると「最上位の 1」が消えて小さくなるのだ。よって 1 回でできる。

ちゃんと見積もってみる。今回の制約では、最大でも 31 桁なので、 $N \ge 63 (= 31 \times 2 + 1)$ とすれば、鳩の巣原理より、「最上位の 1 の桁」が一致する 3 整数が存在することになる。

よって、次のようにすれば OK。

$N \le 100$ 程度では $O(N^{3})$ の全探索
$N \gt 100$ では 1 が答え

コード

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

int N;
vector<long long> A, S;
const int INF = 1<<29;

long long naive() {
    int res = INF;
    for (int a = 0; a < N; ++a) {
        for (int b = a+1; b <= N; ++b) {
            for (int c = b+1; c <= N; ++c) {
                if ((S[a]^S[b]) > (S[b]^S[c])) {
                    res = min(res, c-a-2);
                }
            }
        }
    }
    return (res < INF ? res : -1);
}

long long solve() {
    if (N < 500) return naive();
    else return 1;
}

int main() {
    while (cin >> N) {
        A.resize(N), S.assign(N+1, 0);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
            S[i+1] = S[i] ^ A[i];
        }
        cout << solve() << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #687 (Div. 1) B. XOR-gun (R2000)

問題概要

制約

考えたこと

実はほとんど 1 回や 2 回でできるのでは

コード