きままにものづくり

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

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)

コード

広告を非表示にする