ECR152-F XOR Partition - zawatinはてなブログ

問題

https://codeforces.com/contest/1849/problem/F (diff 2700)

非負整数の集合 $S$ に対して、 $S$ のスコアを $S$ の相異なる二要素のxorとしてあり得る最小値とする。ただし、 $|S| = 1$ の場合スコアは $2^{30}$ とする。

相異なる $N$ 個の整数 $a_{1}, a_{2}, \dots, a_{N}$ を与える。二つの空集合 $S, T$ を用意し、各 $a_{i}$ をどちらか片方に挿入する。 $\min(Sのスコア, Tのスコア)$ としてあり得る最大値を達成する操作方法を一つ求めよ

制約

$2\ \le\ N\ \le\ 2\times 10^{5}$
$0\ \le\ a_{i}\ \lt\ 2^{30}$
TL7.5秒

解法

この問題をグラフで言い換えると以下のような問題になる。

$N$ 頂点のグラフがあり、各頂点 $u, v$ には重み $a_{u}\oplus a_{v}$ の辺が張られている。

グラフの各頂点を二色で塗り分ける。このとき同じ色で塗られた頂点を結ぶ辺のコストの最小値としてあうる最大値を達成する塗り分け方を一つ求めよ。

二分探索をしろという見た目をしているので、適当な判定問題を考える

判定問題解は $x$ 以上か？

辺のコストが $x$ 未満の辺の両端点を異なる色で塗り分ける必要がある。よって、辺のコストが $x$ 未満の辺のみを考慮したグラフが二部グラフであることが解が $x$ 以上である必要十分条件である。

[この判定問題を一回解くことを高速化することは難しい。

そこで、 $x = 0, 1, 2, \dots$ の順に判定問題を解くことを考える。「解は $x$ 以上か？」を解くために「解は $y\lt x$ 以上か？」の判定問題で利用したものを使いまわす *1

判定問題2

コストが $x$ 未満の辺のみを張ったグラフが与えられて、これが二部グラフであると仮定する。

このグラフにコストが $x$ の辺を張って、二部グラフならYes

これをそのまま行ってもグラフに辺は $\binom{N}{2}$ 個あるためまだ遅い。

ところで、判定問題中に張ろうとしている辺 $(u, v)$ について $u, v$ が既に同じ連結成分なら実際に張らなくても良い。

$u, v$ が同じ連結成分で同じ色で塗られているなら、判定問題は即座にNoを返す
そうでないなら、彩色に影響が無いため無視して良い

以上からグラフの最小全域木を作成して、この木上で塗り分けをすると解を達成できる。

$(u, v)$ に $a_{u}\oplus a_{v}$ の重みが張られたグラフ上の最小全域木を求める問題は有名問題らしい。

ブルーフカ法をベースにやる
頂点 $v$ に対して $a_{u} \oplus a_{v}$ が最小となるような $u$ を発見するのはBinary Trieでできる
各連結成分について、「連結成分上の頂点 $v$ についてBinary Trieから $a_{v}$ を削除する」-> 「各頂点について最小の辺を求める」-> 「張る」-> 「Binary Trieに要素を戻す」
$O(n\log \max a)$ かかるステップを $O(\log n)$ 解解くことになる。TL7.5秒を考慮して、これは間に合うと予想できる

実装

#include <bits/stdc++.h>

#include "Src/Template/IOSetting.hpp"
#include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"
using namespace zawa;

struct Node {
    int val{};
    int num{};
    int ch[2]{ -1, -1 };
    Node() = default;
    Node(int v) : val{v}, num{} {}
};

std::vector<Node> Trie;

int MakeNode(int v) {
    int res{(int)Trie.size()};
    Trie.emplace_back(v);
    return res;
}

void Insert(int v) {
    int now{};
    int val{};
    for (int i{29} ; i >= 0 ; i--) {
        assert(now < (int)Trie.size());
        Trie[now].num++;
        if (v & (1 << i)) {
            val |= (1 << i);
            if (Trie[now].ch[1] == -1) Trie[now].ch[1] = MakeNode(val);
            now = Trie[now].ch[1];
        }
        else {
            if (Trie[now].ch[0] == -1) Trie[now].ch[0] = MakeNode(val);
            now = Trie[now].ch[0];
        }
    }
    Trie[now].num++;
}

void Erase(int v) {
    int now{};
    for (int i{29} ; i >= 0 ; i--) {
        assert(now != -1);
        assert(now < (int)Trie.size());
        assert(Trie[now].num > 0);
        Trie[now].num--;
        if (v & (1 << i)) now = Trie[now].ch[1];
        else now = Trie[now].ch[0];
    }
    Trie[now].num--;
}

int FindMin(int x) {
    int now{};
    for (int i{29} ; i >= 0 ; i--) {
        assert(now != -1);
        assert(now < (int)Trie.size());
        assert(Trie[now].num > 0);
        int flag{x & (1 << i) ? 1 : 0};
        if (Trie[now].ch[flag] == -1 or Trie[Trie[now].ch[flag]].num == 0) flag ^= 1;
        now = Trie[now].ch[flag];
    }
    assert(now != -1);
    assert(now < (int)Trie.size());
    assert(Trie[now].num > 0);
    return Trie[now].val;
}

int main() {
    Trie.push_back(Node{});
    SetFastIO();

    int n; std::cin >> n;
    std::vector<int> a(n);
    std::set<int> set;
    std::map<int, int> inv;
    for (int i{} ; auto& x : a) {
        std::cin >> x;
        Insert(x);
        inv[x] = i;
        i++;
        // std::cout << x << ' ';
    }
    DisjointSetUnion dsu(n);
    std::vector g(n, std::vector<int>{});
    while ((int)dsu.size(0) < n) {
        // std::cout << "iteration start" << std::endl;
        auto comp{dsu.enumerate()};
        std::vector<std::tuple<int, int, int>> next(comp.size(), { (1 << 30) + 1, -1, -1 });
        for (int i{} ; const auto& c : comp) {
            // for (auto x : c) assert(Contains(a[x]));
            for (auto x : c) Erase(a[x]);
            for (auto x : c) {
                int v{FindMin(a[x])};
                if (std::get<0>(next[i]) > (a[x] ^ v)) {
                    // std::cout << "find " << x << " -> " << v << std::endl;
                    next[i] = { a[x] ^ v, x, inv[v] };
                }
            }
            for (auto x : c) Insert(a[x]);
            i++;
        }
        for (int i{} ; i < (int)comp.size() ; i++) {
            auto [cost, u, v]{next[i]};
            if (cost == (1 << 30) + 1) continue;
            if (dsu.same(u, v)) continue;
            // std::cout << u << ' ' << v << " merge " << std::endl;
            dsu.merge(u, v);
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        }
    }
    std::vector<int> col(n, -1);
    auto dfs{[&](auto dfs, int v, int c) -> void {
        col[v] = c;
        for (auto x : g[v]) if (col[x] == -1) dfs(dfs, x, c ^ 1);
    }};
    dfs(dfs, 0, 0);
    for (int i{} ; i < n ; i++) std::cout << col[i];
    std::cout << '\n';
    // 42 13 1337 37 152
    // 00011
}

感想

diffが鬼高いが、公式解説に「典型テクを説明しているよ！」みたいな文言を発見したので読んで実装してみた。
Binary Trieを再帰で書こうとしたら実装を壊してしまった。引退。
この問題の見た目でこれとかの有名事実を利用しない解法があってそれが想定なのがびっくりした。プロびっくり屋。

*1:並列二分探索みたいだね。何も並列していないが...