キーエンスプログラミングコンテスト2019-E Connecting Cities

お久しぶりです．今回は日本語でのブルーフカ法によるConnecting Citiesの解説が見当たらなかったので筆を取りました．たくさんの解法がある(けんちょんさんblog参照)ので色々検討すると面白いと思います．

ブルーフカ法 - Wikipedia 参照．簡単に言えば全頂点からのプリム法．計算量はO(E logV)．

辺を貪欲に張っていくことを考える．すると重要な考察として，以下の左図のように辺が交差する辺の張り方は，右図のように交差しないように張り替えた方がより効率が良いことがわかる．

この事実から，全ての頂点から最小コストの辺を張ると(すなわちブルーフカ法の1周目を行うと)，連結しているものは全て連続区間であることが導かれる．

更に，連続区間もまた頂点と同様に考えられるので連続区間同士でまた最小コストの辺を結ぶ...という操作を繰り返すと自然と最小全域木(MST)が得られる．これは上で触れたブルーフカ法に他ならない．

ここで重要なのは，連結成分が連続区間なので，左右それぞれについて最小コストの辺はSegment Tree, Sparse TableなどによってO(log N)で求められるということである．

以上の考察により，MSTはO(N(logN)^2)で得られる.

連結判定をUnionFind,辺選択をSparseTableで行った．以下実装リンク