---
# System prepended metadata

title: AHC017

---

# AHC017

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

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

## 案

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

## 最悪のパターン
ｷﾚｲﾀﾞﾅｰ
![](https://i.imgur.com/5jN9d5z.png)

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

![](https://i.imgur.com/iIAmGWR.png)
![](https://i.imgur.com/PUVn68C.png)

