AHCお疲れさまでした、501,414,836点、2位でした

解法は、　「一つの塔を選んで、カバーする家が一つづつ増えるようにMAXまで出力を増加させながら、それによりほかの塔が出力減少する」を遷移とした焼きなましでした。

シュタイナー木は求めるのに時間がかかるので、　遷移に入れずに、　最後に塔の集合を求めてからシュタイナー木をしました。　

シュタイナー木の求め方はプリム法をつかった貪欲をしました。 コンテスト後に発見しましたが、シュタイナー木のライブラリを使った方がよかったかもしれません https://github.com/wata-orz/steiner_tree

焼きなまし1stepごとにキャッシュを持ちながらシュタイナー木を求めた方が、シュタイナー木のコストも考慮できるのでよかったかもしれません

工夫した点として、　焼きなましの序盤は、　点がまとまった部分を1点にまとめることで高速化しました

あとは、実行時間が余ったので、焼きなましを4回やって一番いいのを選択するのも有効でした