Skip to content

THIRD プログラミングコンテスト 2021(AtCoder Heuristic Contest 007)

問題概要

  • 頂点数 N、辺の数 M の無向グラフがあり、辺 i の長さ l は、頂点間のユークリッド距離を d とすると、d <= l <= 3 * d であるが、正確な値は最初はわからない
  • ターン i では、辺 i の正確な距離が与えられるので、その辺を選択するか否かを答える
  • 最終的に選んだ辺が全域木になっており、その選択した辺の長さの合計が最小になるようにせよ

時間

240 分

個人的メモ

  • 毎ターン、その辺を選択した/選択しなかった場合の「最終的な最小全域木の総距離の期待値」を計算できれば、期待値が低くなる場合に選択、そうでないなら選択しない、とする greedy が考えられる
  • 期待値を正確に算出するのは難しいので、近似的に求めることになる

近似の仕方

  • l=2d を仮定
    • https://www.terry-u16.net/entry/ahc007-explanation
    • 残りの不明な辺の長さを l=2d と仮定するのは、実はそんなに良い解が得られない
    • 目指している解では l=d に近い辺を採用しているはずなので、大きめに期待値を計算している可能性
    • 2 じゃなく少し小さめの値にすると少しだけよくなる
  • モンテカルロ法
    • 長さが不明な辺に対して実際に値を割り当ててみたものをいくつか用意して、コスト平均を見る
  • wataさんの DP 解

その他の方針

  • 辺の採用確率
    • ランダムに辺の長さを割り当てたグラフをいくつか用意して最小全域木を計算
    • 作った最小全域木でその辺が採用される確率が X 以上なら採用

その他

解説

(50 位まで&発言を見つけられた方のみ)