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]


ファイルを添付する

fileizumi_E.cpp 916件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: fileizumi_E.cpp 916件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:36 (4343d)