Supercomputing Contest 2012

都市伝説:不可思議トライアングル

大都市の複雑な電車網では,1日中電車に乗っている2人が,まったく出会わない,ということも十分起こりうる.たとえ,それが3人であってもだ.

非出会い系最長乗車パターン

ある都市の電車網(例:下図)における1日の電車の運行スケジュールが与えられる.そこから,3人が,始発から終電まで1度も同じ駅で出会わないような電車の乗り方のうち,3人の合計走行距離が最も長くなるものを求めよ.

honsen2012_ex.png
駅数20の小規模な例

条件

  • 電車は分刻みで運行
  • 1日は4:00〜24:00の20時間 (1200分間)
  • 駅の停車時間は0分。また、0分で乗り換えも可能。
  • 急行、快速などもあり、超複々線。
  • ある時刻に同じ駅にいるだけでなく、同じ駅に止まる電車にのっていても出会ったとみなす。

添付ファイル: filehonsen2012_ex.png 551件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-10-01 (月) 11:51:52 (1786d)