問題

方針

放送局の電波の強さを焼きなましで求める
使用する放送局を頂点とした最小全域木を求める

電波の強さを焼きなましで求める

各放送局の電波の強さを焼きなましで求めました。遷移としてはランダムな放送局を 1つ選んで電波の強さを変化させます。出力強度は 0 から 5000 までの値をとれますが無駄な変化を避けるためにあらかじめ「このぐらいの強さならこの領域をカバーできる」という情報を計算しておいて、カバー領域が変わらない部分についてはまとめるようにしています。

この計算をしておくことで、電波の強さを変化させたときに「カバー領域が変化しない」ということを避けることが出来ます（この場合は変化のパターンは 0, 250, 450, 700 の 4パターンに限定する）。また、50% の確率でその放送局の出力強度を 0 にします。まとめると以下の通りになります。

50% の確率で出力強度を 0 に変化させる
それ以外はランダムに出力強度を変化

変化させるなかでスコアが一番高くなった状態を採用します。

最小全域木の計算

使用する放送局が求まったらそれらを頂点とした最小全域木を作成します。使用する放送局間が直接繋がっていない場合はダイクストラで求めた経路で使用する辺をまとめて 1つの辺として扱います。

2 つの基地局を接続する際には辺をまとめて採用する。

2 つ基地局を接続したら再度辺のコストの計算を行います（すでに採用した辺のコストを 0 とする）。毎回やると計算量が大変なことになりそうですが軽く調べた感じ放送局の平均使用数が大体 10個前後ぐらいなのであまり問題にはなりませんでした。

複数回実行

先程までの処理を 1ループとして時間制限が来るまで複数回行いました。正直時間が足りなくて悪あがき的な実装なのであまりよろしくないです。

感想

ビジュアライザ見た感じ電波の強さの調整とか木の構築とかいくらでも改善点ありそうな感じだったけど時間足りなくてパラメータガチャに走ったのは残念。短期コンだと事前準備しておかないと「調査して」「実装探して」「試してみる」みたいな時間が取りにくいから、自分みたいな実装が遅い人だと持ってるライブラリがあるかないかで大分変わってしまう。

最後に宣伝。今週から Marathon Match 146 が始まります。