Problem D

Problem D:
So Sleepy
解答：寺島・平野
英文：八森
解説：寺島
解答状況
Submitted : 30 (14 teams)
 Solved : 12
 First Accepted : 110 min (Prime)

問題概要

会議までにどれだけ電車で眠れるか
 時刻表が与えられる
 一本の電車でしか眠れない
 電車の外では眠れない
解法 - Dijkstra (1)

各駅の最速到着時刻を求める
 出発駅・時刻から変形ダイクストラ
 目的地に会議の時刻までに到達できなけれ
ば ”impossible”

各駅の最遅出発時刻を求める
 到着駅・時刻から逆向きに
解法 - Dijkstra (2)

各電車について
 出発時刻が最速到着時刻以降となる最初の駅か
ら，到着時刻が最遅出発時刻以前となる最後の
駅まで眠ることができる
 最大の眠り時間を求める

O(ST log T)
解法 - DP (1)
各駅の最長睡眠時間と各電車の最長乗車時
間，最長睡眠時間をテーブルで保持
 時刻の早い発着から順にテーブルを更新して
いく

 同時刻の場合は到着の方を先に処理する

O(ST log T)
解法 - DP (2)

テーブル更新のルール
 出発
- その駅に到達可能な場合
電車の乗車時間 += 次の区間
 電車の睡眠時間 >?= 駅の睡眠時間

 到着
電車の睡眠時間 >?= 電車の乗車時間
 駅の睡眠時間 >?= 電車の睡眠時間


Download Report