https://atcoder.jp/contests/arc021/tasks/arc021_4
- 考えたこと
- ほぼ最小な全域木を作れっていう奇妙な問題
- 最小全域木をクラスカル法で求める場合O(ElogE)
- 点が5000あるので辺は10^7くらいある
- ちょっと厳しいか。距離の計算に200掛かるし。
- 入力がランダムであることが保証されてるのが肝か
- まず点をおよそ半分に分ける
- 一軸に注目して正負で分ければ良い
- 辺は1/4になるのでクラスカル法のコストは半分になる
- 分けたものをつなぐコストが、最良の辺を見つけようとすると高いけど、これは適当につないで大丈夫、最良の場合と比べて高々2しか悪くない
- 実際には次元の呪いでほとんどすべての点の距離が1付近
- 半分で間に合うようになるのかはよくわからない
- 間に合わないならもっと細かく割る必要がある
- サンプルの最小スコアから判断して、16個に割って適当につないでも大丈夫
- 公式解説
- 200次元なので200個に割ってる
- それをやって最適解の1.01倍に収まることの証明はしないのか…