https://atcoder.jp/contests/abc065/tasks/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オーダーで間に合わない時には辺を削減できないか考えるべきか
- 辺の削減→最小全域木
- 隣だけを見れば良い