問題概要

$N$ 個の非負整数 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。ある非負整数 $x$ を上手に選んだときの、

$\max(A_{1}$ $\mathrm{xor}$ $x, A_{2}$ $\mathrm{xor}$ $x, \dots, A_{N}$ $\mathrm{xor}$ $x)$

の値の最小値を求めよ。

制約

$1 \le N \le 1.5 \times 10^{5}$
$0 \le A_{i} \lt 2^{30}$

考えたこと

この問題のように、数列全体の 2 進法表記を考えたい問題では、下図のように「上位桁から再帰的に 0 と 1 とで分岐していく木」を作るとうまくいくことが多いです！！！ (Binary Trie とも呼ばれるものです)

辞書順で考える

数値を最小にするとは、各桁の値を上位桁から並べたときに辞書順最小を求めるということでもあります。よって、上位桁から順に Greedy に小さくしていくことを考えます。

ここで上図の場合を例にとって考えてみましょう。上図の場合、 $2^{5}$ の桁の値はすべて 1 で等しいので、 $x$ の $2^{5}$ の桁の値を 1 にして XOR をとることで、 $N$ 個の値の $2^{5}$ の桁の値をすべてまとめて 0 にすることができます。

一方、 $2^{4}$ の桁については、0 と 1 とが混在しているため、すべてを 0 にすることはできません。しかし上図の「 $2^{4}$ の桁が 0 であるグループ」と「 $2^{4}$ の桁が 1 であるグループ」のうち、片方を 0 にして、他方を 1 にすることができます。 $2^{3}$ の桁以下の部分の結果をより小さくできる方のグループを選んで、 $2^{4}$ の桁を 1 にする方がよいでしょう。

一般に、上位の桁から見ていき、次の疑似コードのような再帰解法で解けそうです。つまり、上図の「再帰的に上位桁から 0 と 1 で分類した木」の各ノードを再帰的に深さ優先探索していることになります。

// 整数値の集合 A に対して、2^d 桁目以下の部分について
// x との XOR をとったときの最大値の最小値を返す
long long rec(int d, const vector<int>& A) {
    // 終端条件
    if (d == -1) return 0;

    if (A の 2^d 桁目がすべて等しい) {
        // 2^d 桁目をすべて 0 にできる
        return rec(d-1, A);
    } else {
        vector<int> one = A のうち 2^d の桁が 1 のものを集めた集合;
        vector<int> zero = A のうち 2^d の桁が 0 のものを集めた集合;

        // one と zero について再帰的に解いて小さい方の 2^d 桁の値を 1 にする
        return (1<<d) + min(rec(d-1, one), rec(d-1, zero));
    }
}

この解法は、一見計算量が爆発しそうに見えますが、上図の再帰木の深さを $D$ として、

各 $d = 0, 1, 2, \dots, D-1$ に対して
数列 $A_{1}, A_{2}, \dots, A_{N}$ の値を 1 回ずつ眺める

ような処理になっています。

再帰木の深さは、 $M = \max(A_{1}, A_{2}, \dots, A_{N})$ として $D = O(\log M)$ と評価できますので、全体の計算量は $O(N \log M)$ であると考えられます。

コード

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

long long rec(int d, const vector<long long>& A) {
    // 終端条件
    if (d == -1) return 0;

    // A のうち、2^d の桁が 1 のものと 0 のものに分ける
    vector<long long> one, zero;
    for (const auto val : A) {
        if (val & (1LL<<d)) one.push_back(val);
        else zero.push_back(val);
    }

    if (one.empty() || zero.empty()) {
        // A の 2^d 桁目がすべて等しいときはすべて 0 にする
        return rec(d-1, A);
    } else {
        // one と zero について再帰的に解いて小さい方の 2^d 桁の値を 1 にする
        return (1LL<<d) + min(rec(d-1, one), rec(d-1, zero));
    }
}

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    cout << rec(30, A) << endl;
}