まず初期解を構築して、その後 \(P_{i}\) の値を微小変化させて焼きなまします。

ここで、 \(dist(x,y)\) で放送局 \(x\) と住民 \(y\) の距離とします。

初期解

まず、最小全域木を作ります。

その後、\(1\leq j\leq K\) に対して、 \(i=\argmin(dist(i,j))\) を求めて \(P_{i}\leftarrow\max(dist(i,j))\) と更新し、放送局 \(i\) が 住民 \(j\) を担当しているという情報を持ちます。

そして \(P_{i}=0\) かつ葉であるものを最小全域木から外し、放送局自体を今後一切使用禁止にするという操作をします。

これで 416.1M 程度の得点が手に入ります。

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

更新

この初期解をみたらわかるのですが、一人しか担当していない放送局が存在しているところに無駄があると感じます。

これを \(0\) にして、担当していた住民を他の使用禁止になってない放送局に担当してもらうという更新が考えられます。

\(0\) にする放送局を、担当している人数の二乗の逆数に比例するようにして選び続ける山登りをすると 454.7M のスコアが出ます。

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

しかし、この操作は変化が大きいかつ不可逆チックなので、焼きなましすることが難しいです。

よってより微小な変化を考えます。

• 担当している住民がいる放送局のうちランダムに一つ選んで \(i\) とする。放送局 \(i\) が担当してる住民のうち一番遠い住民を、コストが一番かからない使用禁止になっていない他の放送局に託す

この操作をすると、 \(P_{i}\) が下がり、託された放送局の \(P\) は上昇します。

\(P_{i}\) が \(0\) になって、かつ全域木のコストが軽くなるなら適時 \(i\) を使用禁止にします。

この操作はスコアが差分更新することができるのでスコアの計算量は小さいです。

操作自体は放送局 \(i\) が担当している住民の数を \(X\) として \(O(N+X)\) です(多分)。

この操作で山登りをすると 487.6M が出ます。

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

焼きなましをすると 495.5M (本番中は少しミスって 495.1M) が出ます。

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