こどふぉのこの回、いい問題が多かった気がするので解き直し。最上位の桁から順に見ていって、0 と 1 とに分類していって...とするのはよく見る気がする！！！

問題へのリンク

問題概要

どの要素も互いに相異なる非負整数列 $B_{1}, \dots, B_{M}$ が good であるとは、以下の条件を満たすことと定義する。

数列の各要素を頂点に対応させたグラフを考える
各 $i$ に対して、 $B_{i}$ XOR $B_{j}$ が最小となるような $j (\neq i)$ を $k$ としたとき、頂点 $i$ と頂点 $k$ を辺で結ぶ (向きなし, 多重辺は認める)
このように定義したグラフが連結である

今、 $N$ 要素の互いに相異なる非負整数列 $A_{1}, \dots, A_{N}$ が与えられる。この数列からいくつかの要素を除去することで、good となるようにしたい。除去すべき要素数の最小値を求めよ。

制約

$2 \le N \le 2 \times 10^{5}$

考えたこと

状況がよくわからないので色々手を動かして考えてみる。たとえば

といったケースを考えてみる。このとき、前半 2 つと、後半 3 つとでそれぞれ連結成分を形成している。そのようになる理由を考察してみた。

まず、4 つの整数 $A, B, C, D$ に対して、ある桁 $d$ が存在して

$d$ 桁目より上の桁の値はすべて等しい
$d$ 桁目については、 $A, B$ は 0 で、 $C, D$ は 1 である

という状況にあったとする。このとき、 $(A, B)$ グループと、 $C, D)$ グループとが、グループの垣根を超えて辺で結ばれることはない。なぜなら、同一グループ間で辺を結んでおけば、 $d$ 桁目も含めてそれより上の桁はすべて 0 にできるからだ。

ゆえに、すべて連結にするためには、 $d$ 桁目が「0 のグループ」と「1 のグループ」のうちの少なくとも一方がサイズ 1 以下になる必要がある。

上位桁から再帰的に木を作る

これはこどふぉだと、本当によくみる視点だと思う。上位桁から順に見ていって、

$d$ 桁目について、

「0 グループ」を連結にして、「1 グループ」のサイズを 1 にする
「1 グループ」を連結にして、「0 グループ」のサイズを 0 にする

という 2 つの場合のうち、答えが小さい方を返すようにすればよい。そして各グループを連結にする問題は、再帰的に解くことができる。

再帰深度は高々 31 (最大桁数) 。計算量は $O(N \log A)$ となって十分間に合う。

コード

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

int N;
vector<long long> A;
int DIGIT = 32;
long long solve(int left, int right) {
    if (right - left <= 1) return 0;
    int d = DIGIT;
    for (; d >= 0; --d) {
        bool f1 = (A[left] & (1LL<<d));
        bool f2 = (A[right-1] & (1LL<<d));
        if (f1 != f2) break;
    }
    int mid = left;
    for (; mid < right; ++mid) if (A[mid] & (1LL<<d)) break;
    return min(solve(left, mid) + (right - mid - 1),
               solve(mid, right) + (mid - left - 1));
}

int main() {
    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    sort(A.begin(), A.end());
    cout << solve(0, N) << endl;
}

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

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

Codeforces Round #683 (Div. 1) C. Xor Tree (R2100)

問題概要

制約

考えたこと

上位桁から再帰的に木を作る

コード