AHC017

どう考えてもまともな貪欲が必要だけど，グラフを分割するのがめんどくさすぎる
絶対スコアが低いほうが良い相対スコアが出て？？？になってたらそういうコンテストだった カス

最終解

• u→vへの最短パスを取り除く
  * 最短パスと同じ辺数の迂回路？
  • 閉路ができるとだめ
  • 次数分辺を生やすとだめ
  • 隣の道を同じ日に取るとスコアが下がりやすい
  • 最初に道を作ってから割り振る←やってない
    • 縦の道と横の道
    • 外周から剥いでいく

案

• クラスタ内の辺の中心座標間の距離のminの最大化
• 中心座標じゃなくてグラフ上の距離にする
• 一番遠いところに割り振る貪欲をやる
• 辺を座標 m / d 分割して各クラスタから1日1つ
• nとdを軸にプロットして初期値と比較する
• MSTを取ってそれ以外を削除
  • 割当が難しい
  • MST を d区画に分けて削除
  • mst を削除する区画はそれ以外を残す
• ランダムな木を除外

最悪のパターン

ｷﾚｲﾀﾞﾅｰ

最高のパターン

焼きなましを24時間を回した
どう考えても木を取り除いている気がするが，なんでこれがいいんや
木というか最短パスを取り除いてるっぽい？