CC200 - MINSET

upsolveにあたって解説の内容をちゃんと理解したかったので文字に起こしたログ。どちらかというとメモ用に近くて、Editorialの内容そのまま(か不足がある)ぐらいのものです。

問題概要

正整数$N$が与えられます。以下の条件を満たす集合$S=\{(A_1, B_1) \cdots (A_{|S|}, B_{|S|}\}$を「良い集合」と呼びます。

• $1 \leq A_i, B_i \leq N (i=1, \cdots, |S|)$
• 長さ$N$の順列$P$としてあり得るものすべてについて、以下の操作を繰り返すことでソートされた状態にすることができる
  • $i (1\leq i \leq |S|)$を選び、$P_{A_i}とP_{B_i}$を入れ替える

良い集合について、そのスコアを$\sum_{i=1}^{|S|} A_i \oplus B_i$で定めます。達成可能なスコアの外界を求めてください。

Codechef MINSET

解法

まず、条件の2を満たすような集合がどのようなものかを考えると、(割とすぐに思いつくのが)$A_i, B_i$を辺として見て、$N$頂点$|S|$辺からなるグラフが連結であるかどうかが条件になっていそうである。実際にこれは正しい。

ある2頂点$u, v$を繋ぐ辺のコストは$u \oplus v$で定められているので、この問題はグラフの最小全域木を求める問題に帰着できる。

ここで、$K$を$2^K \leq N$を満たす最大の$K$と定義する。このとき、頂点を$[1, 2^K - 1]$と$[2^K, N]$の2つの集合に分けると、この2集合を繋ぐ辺が1つ必要になる。このときにコストを最小とするような辺が何かを考えると以下のようになる。

• $N=2^K$の場合: $1$と$2^K$をつなぐ場合で、コスト$2^K+1$
• そうでない場合: 1と$2^K + 1$を繋ぐ場合で、コスト$2^K$

続いて、$[1, 2^K - 1]$と$[2^K, N]$のそれぞれの集合でMSTを構成する方法を考える。前者について¹については、$N=2^K-1$と置き直して上記の手法を再帰的に適用することでコストを求めることができる。後者については$K$の取り方から、どの2点をとっても最上位のbitがxorにより0になるため、区間を$[0, N-2^K]$と置き直すことができる。

ここで、集合の最小値がゼロの場合、つまり頂点番号$0$を含む$R+1$頂点のグラフを構築する場合に、コストがどうなるかを考える。基本的には同じように考えれば良くて、$2^{K^\prime} \leq R$以下の$K^\prime$を選んで分割をし、その2つの集合をコスト最小で繋ぐ辺を追加していけば良い。このコストは、頂点$0$と頂点$2^{K^\prime}$を選択することでコスト$2^{K^\prime}$で繋ぐことができ、また分割の仕方を考えるとこの繋ぎ方が最適である。分割後の集合は$[0,2^{K^\prime}-1]$, $[2^{K\prime}, R]$となり、後者は先程同様の議論で$[0, R-2^{K^\prime}]$と同一視できる。よって、同じ手法を再帰的に適用することで全体を繋ぐコストを求めることができる。

ここまでの議論から、

集合$\{1, 2, \cdots, x\}$に対してMSTを構築するときのコストを$f_1(x)$ 集合$\{0,1,2,\cdots, x\}$に対してMSTを構築するときのコストを$f_0(x)$

と定義すると、以下のように計算することができる。ただし、$K$は$2^K \leq x$を満たす最大の$K$である。

• $f_0(x) = 2^K + f_0(2^K-1) + f_0(x-2^k)$
• $f_1(x) = 2^K + [x=2^K] + f_1(2^K-1) + f_0(x-2^K)$

ただし、$[x=2^K]$は$1 \text{ if } x=2^K, \text{ otherwise } 0$を表す²。また、$f_0(1) = 0, f_1(1) = 0$である。

求めるべきは$f_1(N)$である。これはそのまま実装すると$O(N)$となるが、適切にメモ化することによって$O(\log N)$で求めることができる。提出

fn f0(x: usize, memo0: &mut HashMap<usize, usize>) -> usize {
    if x == 0 {
        return 0;
    }
    if x == 1 {
        return 1;
    }

    if let Some(val) = memo0.get(&x) {
        return *val;
    }
    
    let mut v = 1;
    while v * 2 <= x {
        v *= 2;
    }
    
    let res = v + f0(v-1, memo0) + f0(x-v, memo0);
    memo0.insert(x, res);
    return res;
}

fn f1(x: usize, memo0: &mut HashMap<usize, usize>, memo1: &mut HashMap<usize, usize>) -> usize {
    if x <= 1 {
        return 0;
    }
    
    if let Some(val) = memo1.get(&x) {
        return *val;
    }
    
    let mut v = 1;
    while v*2 <= x {
        v *= 2;
    }
    
    let res = v + f1(v-1, memo0, memo1) + f0(x-v, memo0) + if x==v { 1 } else { 0 };
    memo1.insert(x, res);
    return res;
}

fn solve(ip: &mut Input) {
    let n = ip.next::<usize>();
    let ans = f1(n, &mut HashMap::new(), &mut HashMap::new());
    println!("{}", ans);
    
}

ムズいだろ！