UTPC 2013 F - 魔法の糸

• 問題
• AC
• AC (bin sort)

解説を見てACしたのだが、実装でつまづいた……というか、計算量がよくわかっていなかったのでメモ。

頂点$p$を含む連結成分$V(p)$と頂点$q$を含む連結成分$V(q)$を併合するとき、$V(p)$と$V(q)$の間の辺をどう集めるかが問題になるが、重みを隣接行列にでも記録しておいて、単に$V(p)$の頂点と$V(q)$の頂点のペアを総当たりすればよい。こうすると、この部分の計算量が$Q$回の更新で${\mathcal O}(N^2Q)$になってしまいそうな気がしていたのだが、よく見ると1つの頂点ペア$\{v, w\}$につき高々1回しか処理されていないので、${\mathcal O}(N^2+Q)$で済んでいる。

全体の計算量について。Kruskal法の前に辺の長さでソートする部分がボトルネックになる。頂点$p$, $q$を結ぶ$i$個目のクエリに対して、$V(p), V(q)$の間の辺が$d_i$本あったとすると、上で述べたように$d_1+ ... + d_Q \le M$である。また、以前のクエリで$V(p)$の最小全域木を作ろうとした時に選んだ辺は高々$|V(p)|$であり、$V(q)$についても同様に$|V(q)|$である。$|V(p)|+|V(q)| \le N$だから、$i$個目のクエリで扱うべき辺の数は高々$N+d_i$本となる。したがって、$Q$回のソートの計算量は

$\begin{aligned} & {\mathcal O} \bigl (\sum_{i=1}^Q(N+d_i)\log(N+d_i) \bigr) \\ = & \: {\mathcal O} \bigl (\sum_{i=1}^Q(N+d_i)\log N \bigr) \\ = & \: {\mathcal O} \bigl (\sum_{i=1}^Q N \log N + \sum_{i=1}^Q d_i \log N\bigr) \\ \subseteq & \: {\mathcal O} \bigl (QN \log N + M \log N\bigr) \\ \subseteq & \: {\mathcal O} \bigl ((N^2 + M) \log N\bigr). \end{aligned}$

ソートの部分はバケットソートでも通って計算量は${\mathcal O}(N^2+M+Q\max w_i)$となる……けど、別に速くはならない。