バチャ中に TLE が取れなかった...
$O(N \log N \log A)$ で実装してしまっていたけど、 $O(N \log A)$ にする必要があったみたい。

問題へのリンク

問題概要

長さ $N$ の 0 以上の整数からなる数列 $A_{1}, \dots, A_{N}$ が与えられる。

0 以上の整数 $x$ を適切に定めて

$B_{i} = A_{i}$ XOR $x$

で定まる数列 $B_{1}, \dots, B_{N}$ の転倒数が最小となるようにせよ。転倒数が最小になる場合が複数通り考えられるならば、そのうち $x$ が最小のものを答えよ。

制約

$1 \le N \le 3 \times 10^{5}$

考えたこと

例によって、上位桁から順に見ていくとなにかわかったりするのかなと考えた。

$d$ 桁目を考えているとき、とりあえずそれより上位の桁については値が fix しているものとして、それより上位の桁が等しいもの同士で考えることにする。そしてその中で、 $d$ 桁目が等しいもの同士の転倒数は気にしないことにする (それについてはより下位の桁を考えるときに再考する)。

さて、 $d$ 桁目が 1 であるものと 0 であるものとに分けたとき、

(1, 0) の並びになっている箇所の個数を $P$
(0, 1) の並びになっている箇所の個数を $Q$

とする。なお、 $d$ 桁目より上位の桁が異なる部分についてもすべて総合する。このとき

$P \gt Q$ の場合は、 $x$ の $d$ 桁目は 1 とする
$P \le Q$ の場合は、 $x$ の $d$ 桁目は 0 とする

とすれば OK。重要なことは $d$ 桁目をどう扱うかは、より低位の桁について考えるときにまったく影響しないのだ。よって上位桁から Greedy に考えていけば OK (実際には上位桁からじゃなくても、各桁ごとに完全に独立に考えることができるので、任意の順序でよい)。

各桁 $d$ ごとの $\min(P, Q)$ の総和が求める転倒数の最小値となる。計算量は $O(N \log A)$ ( $A$ を登場する値の最大値とする)。

コード

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

int main() {
    int N;
    scanf("%d", &N);
    vector<int> A(N);
    for (int i = 0; i < N; ++i) scanf("%d", &A[i]);

    int res = 0;
    long long score = 0;
    vector<vector<int>> div(1, A);
    for (int d = 30; d >= 0; --d) {
        vector<vector<int>> nex;
        int mask = 1<<d;
        long long ok = 0, ng = 0;
        for (const auto &v: div) {
            vector<int> zero, one;
            for (auto val: v) {
                if (val & mask) {
                    ok += zero.size();
                    one.push_back(val);
                }
                else {
                    ng += one.size();
                    zero.push_back(val);
                }
            }
            if (!one.empty()) nex.emplace_back(one);
            if (!zero.empty()) nex.emplace_back(zero);
        }
        swap(div, nex);
        score += min(ok, ng);
        if (ok < ng) res += mask;
    }
    printf("%lld %d\n", score, res);
}

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

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

Codeforces Round #673 (Div. 1) C. XOR Inverse (R2000)

問題概要

制約

考えたこと

コード