Member Pilot 2 - てきとーな日記

変則セットだったので450からやってみた
クラスカル法の各段階において求まるものも、そのサイズにおける最適解なので、各段階ごとに連結成分の数だけ空港を置けばよい
そっこーで解けたのに、最後の一回だけ空港0個でいいのをすっかり忘れていて再提出orz
360.50

ただのやるだけゲーだった
276.77

900だから簡単に違いない、と思ったのに解法がわかんねーorz
DPの式を立てたらO(N^3M) (M:文字数)とかなってとても間に合わない…
他の方法があるのかなーと考えたがよく分からず、ちょっと最適化したらMがlogMに減ってなんとか間に合ったｗ
413.18

450で連結成分1の場合を忘れている人が大量にいるに違いないと思ったのにいなかったorz
なんかよく分からないのをランダムでてきとーに撃墜して1ミス1成功
+25.00

合計1075.45の7位