ARC076 D Built?

atcoder.jp

所見  

そういえば解くだけ解いて記事書いてないことに気づいて紅白見ながら慌てて書いています、横ではサザンが歌っておる  

問題概要

座標平面上にN = 10⁵個の町がある。その町をノード、min(x座標の差, y座標の差)をコスト、としたときの最小全域木のコストを答えよ。    

取った方針

N=10⁵なので、クラスカル法が間に合う。しかし、最初に完全グラフを構成するとO(N²)で間に合わない。  

コストがmin(x座標の差, y座標の差)であることに注目すると(ここしか注目するものが無い)、ある町の上下左右直近のものとしか繋がらないことがすぐにわかる。わかるが、上下左右の町を高速に求められず座標が等しいものを削除しようとしたりして死亡  

正しい解法  

上下左右直近のモノと繋ぐには、点をx座標/y座標でそれぞれソートして隣り合うものをつなげばよい。それによりO(N)でグラフを構築できるので間に合うようになる。  

得られた知見  

• 使うアルゴリズムが自明 -> 問題特有の設定に注目  

• x軸とy軸を別々に考えるとO(N²)がO(N)に落ちがち

ギリギリ年明ける前に間に合いました。横ではゆく年くる年が流れています。今年も残すところ10分を切ったところです。    

今年はA*Cの400点を埋めきったので来年は500と600を埋めたいところですね。AtCoder Scores のグラフで物理的な精進量が不足していることが発覚したので量こなしていきたいところです。そして青に…… 青になりたい。

  それではみなさんよいお年を。ﾉｼ