[[Supercomputing Contest 2012]]

* 都市伝説:不可思議トライアングル [#n8465aad]

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

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

CENTER:&ref(./honsen2012_ex.png);
CENTER:駅数20の小規模な例

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


トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS