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) テーブル更新のルール 出発 - その駅に到達可能な場合 電車の乗車時間 += 次の区間 電車の睡眠時間 >?= 駅の睡眠時間 到着 電車の睡眠時間 >?= 電車の乗車時間 駅の睡眠時間 >?= 電車の睡眠時間
© Copyright 2024 ExpyDoc