AHC020の解法解説

概要

使用する放送局の頂点集合を山登りで決めました。
遷移は頂点1個削除です。(最終提出には間に合いませんでしたが、頂点1個追加の遷移と頂点1個削除1個追加の遷移も追加したほうがスコアが伸びました。)
各辺の使用の有無は最小全域木で、パワーは貪欲で求めました。

最終提出(score: 486,037,099)
+頂点1個追加の遷移(score: 493,238,650)
+頂点1個追加の遷移と頂点1個削除1個追加の遷移(score: 493,936,856)

2023/06/12追記
焼きなましに変更し、少しの高速化も行ったらスコアが伸びました。
焼きなまし(score: 496,326,102)

パワーの決定法についての詳細

使用する放送局を決めた後のパワーの決定法についての詳細を説明します。

以下説明で出てくる放送局は使用する放送局のことで、使用をしない放送局は無視します。

• 各家から最も近い放送局とその距離を求めます。
  
• 先ほど求めた距離の大きかった順に対応する放送局のパワーを決定します。
  
• 放送局のパワーは以下のように決定します。
  
  • もし対応する家がすでに他の放送局でカバー済みなら、パワーは変更しない。
    
  • そうでなければ、パワーを対応する家との距離に設定する。
    

このように設定することで、パワーは設定しているがカバーしている家はすべて他の放送局でカバーされているという無駄な状態を(おそらく)軽減することができます。

その他

焼きなましを使わなかった理由

温度のうまい設定方法がわからないからです。