arc076_b
考えたこと
最小全域木を求める問題だが、素朴にやると辺が10^10だからダメ 一番xの小さい頂点に注目する
この頂点は自分以外のどれかとつながらなければならない
xが次に小さい点に繋ぐか、yの近い点に繋ぐか
yの最も近い点が高速に見つけられると良い
でも「xが一定以上で」という条件付きで見つけたいのだよな
yでソートして双方向リストに入れておき、xが小さい方から試した後でそのxを取り除いておけば良い 双方向リストは削除がO(1)だし、前後の値を見るのもO(1)
この時と違ってi番目の要素にO(1)でアクセスしたい
リンクトリストはi番目アクセスが遅いと思いがちだが、それは追加削除した後でのi番目にアクセスする場合であって、削除しかしない場合に追加時のiでアクセスするのはO(1)
これで、前処理O(NlogN)、本処理O(N)になる
公式解説
これは僕の解法で「xでソートして次」だけ見てるのや「yでソートして前後」だけ見てるところでも使っている
各点はx順での前後とy順での前後以外に繋がらない
→辺の本数をNのオーダーまで減らせる
→最小全域木
考察
最小全域木の問題で辺がN^2オーダーで間に合わない時には辺を削減できないか考えるべきか