きままにものづくり

日々の気付いたことなんかを書いてます。

SRM627Div1Medium

問題

N個のノードと無方向性のエッジとノードに対応する数字が与えられる。K個以上のノードをつないだ時のノードに対応する数字の列を考える。この数列(要素数がK個以上)の転換数の最小値を求めよ。転換数とは、Sを得られる数列とした時にiS[j]を満たす(i,j)の数である。

解法

全てのノードに対してDFSを行い、K個以上になった時の転換数を探索していく。愚直に行うと $O(N^4)$ となる。転換数を求めるのに $O(N^2)$ 、DFSを行うのに $O(N)$ 、ノードの数だけDFSを行うので $O(N)$ 、合計して $O(N^4)$ となる。転換数の探索はBITを使用すると $O(log N)$ まで落とせる。

計算量

$O(N^2 log N)$

コード