2005/Contest/国内予選

Problem E : Earth Observation with a Mobile Robot Team †

問題概要 †

解法 †

全体のアルゴリズムは次のとおり．ここに t[i] はロボット i がデータを手に入れる時刻，また S は t[i] の値が未確定なロボット番号 i の集合を表す．

t[1] ← 0
t[j] ← ∞ for j = 2 .. N

S ← {1 .. N}

while (∃j∈S s.t. t[j]≠∞) do begin
    i ← argmin[j∈S] t[j]
    S ← S - {i}
    foreach j∈S do begin
        u[j] ← ロボット i とロボット j が最初に通信可能となる時刻
        t[j] ← min(t[j], u[j])
    end
end

ロボット間の通信が発生する時刻は，ロボット間の距離の 2 乗が区間ごとに時刻 t についての 2 次式となることを利用して計算する．

議論・その他 †

見た目から受ける印象から比べると易しい問題ではある（それでもかなり面倒な問題だと思うが）．添付したコードは少々汚い（というか読みにくい）ので読まれる際は注意されたい．［泉，3 Jul 2005］

実際のデータで正当性を確認しました．［泉，5 Jul 2005］

ファイルを添付する †

izumi_E.cpp