はじめに
AtCoder Heuristic Contest 020 に参加してきましたので、そのときに考えたことを書き連ねています。言ってしまえばあとで見返す（かもしれない）用のメモを推敲もせずに公開しただけ。
初日兼最終日（15 : 00 ~ 19 : 00）
- 初期解
5000 を n 個、1 を m 個並べる（309M 点）
- 第2案
辺に関しては最小全域木で判断。
最も近い放送局が遠い家から順番に、最も近い放送局から電波が届くようにする。
411M 点。
- 第3~6案
（ある家庭に電波が届くようにするために必要なコストの増加量）が小さい順に決定。
放送局 A から電波が届いてる家庭のうち一番遠い家庭が他の電波の範囲に入っていたら A の出力強度を下げる。
辺は最小全域木を出して、各部分木に電波を出している放送局がなければOFFにする。
ここまでで 470M でした。この後もいろいろやったけど点数は上がらず...
調べると最小シュタイナー木とかいうのも出てきたけど、時間もなかったし断念...
延長戦（19 : 00 ~）
コンテスト終了後も提出できるのでちょっとだけやりました。
- 最終案
実行時間が余っているので、解を複数出して最良のものを最後に出力する。
ある放送局からしか電波が届いていない家が一定以下のとき、その放送局は使わない。
辺は最小全域木を出して、各部分木に電波を出している放送局がなければOFFにする。部分木に存在する電波を出している放送局の数に応じてコストを大きくしていく。
478M 点。
左側真ん中の電波を出す放送局１つのために電波を出さない放送局を２つも経由しているのが気になりますが、自分の力ではどうしようもなさそうです...
