arc021_4

考えたこと

ほぼ最小な全域木を作れっていう奇妙な問題

点が5000あるので辺は10^7くらいある

ちょっと厳しいか。距離の計算に200掛かるし。

入力がランダムであることが保証されてるのが肝か

まず点をおよそ半分に分ける

一軸に注目して正負で分ければ良い

辺は1/4になるのでクラスカル法のコストは半分になる

分けたものをつなぐコストが、最良の辺を見つけようとすると高いけど、これは適当につないで大丈夫、最良の場合と比べて高々2しか悪くない

半分で間に合うようになるのかはよくわからない

間に合わないならもっと細かく割る必要がある

サンプルの最小スコアから判断して、16個に割って適当につないでも大丈夫

公式解説

200次元なので200個に割ってる

それをやって最適解の1.01倍に収まることの証明はしないのか…