# AHC020 2023/06/11　15:00～19:00

https://atcoder.jp/contests/ahc020/

## 注意
visualizerで遊ぶ
DFSの手を忘れない
全乱択でもいいから回す

## 所感
コストをかけて領域を広げて、目的のpointをカバーする問題。
全住民に届けるのが大事。
各住民毎に最小コストでの受信を出して、その総和にする？
時間2秒だからかなり厳しい。あまり焼かせる気が無さそう。

各住民毎の最小コスト出して、それらをつなぐ最小全域木を作るのが大事そう。
あとはできてから考えるか。

まずは適当解
最高出力P=5,000でこれ

最小全域木について、これは構築順によって変わってくるので、
住民をシャッフルして何度も構築し直したらよさそう。

貪欲解、これだと中心の重なりが無駄。
また、周辺領域はedgeコストを加味してベストを出しているが、
実施はedgeコストは少なそう

edgeコストを0にしたもの。こっちの方が正しそう。

これをベースに過剰なpowerを削っていく？
範囲内のKを各Pに紐づけ？
距離順にソートして、山登りができるか。

現在、powerが大きすぎる

Pを削除して渡す
Pを追加して奪う

山登りでそこそこいった。

これを焼きなましできるか、した。
今は電波が届かなくなったKは最寄りの放送距離からもらうようにしたけど、
そこに乱数入れてちょっとブラす、→あがった。

終了。ラスサブ、時間ギリッギリで通ってよかった。

最終61位。レートは上がらず。

## 反省会
2p目あたりの人は頂点集合を焼きなまししたっぽい。
そこから、出力強度も焼けるとよいみたい。

最初に全体のMST作って、その辺だけ使うで良かったっぽい。
そうしたら再構築不要になる。

住民を個別にみていたが、凸包として外側だけみたら良かったかも？