ABC 342 E — Last Train

考察

station Bから時刻TまでにNへ到達できると分かっている時、schedule A→Bで使う価値があるのはarrival t+c≤Tを満たす最も遅いdepartureだけである。これにより最新出発時刻を大きい順に確定するDijkstra型探索になる。scheduleのdepartureはl+djで、Bのdeadline Tに接続可能な最大jはmin(k-1,floor((T-c-l)/d))である。j≥0ならそのdepartureがAの候補となり、それより早い同schedule便はlatest値を改善しない。

採用する候補: 逆辺を辿るmax-heap Dijkstraで各stationのlatest feasible timeを求める

等差scheduleから条件内の最終便をO(1)計算し、確定済みstationからpredecessorへ単調に緩和できる。

棄却する候補: 各train便を個別頂点・辺として展開する

一情報あたりk_iが10^9まであり、全便の列挙は不可能である。

各Bに入るschedule情報をreverse adjacencyへ持つ。f[N]=十分大きい∞、他=-∞としてmax-heapにNを入れる。最大Tのstation Bを取り出し未確定なら確定し、各(A→B)について上式のjとcandidate departureを求めf[A]をchmaxしてheapへ入れる。1…N-1を値またはUnreachableで出す。

典型の発動条件

latest-time版Dijkstra

発動条件: 各状態の評価が到達可能な最遅時刻で、後段deadlineから前段の最適時刻が単調に決まる。

min距離の代わりにmax時刻をpriority queueで確定し、逆向きに緩和する。

等差scheduleのfloor検索

発動条件: 大量の出発時刻l,l+d,…に対しdeadline以下の最後の一つが欲しい。

floor divisionでindexを求め0…k-1へclampする。

問題固有の要素

時間を逆向きに見ると「待てるなら早い便より遅い便が常に有利」になり、一scheduleをdeadlineごとの一便へ圧縮できる。

別の問題へ持ち帰る視点: 時刻表最適化では待機可能性を使い、同一路線の支配される便を算術的に選別する。

正当性

到着先の許容最遅Tから逆算した各scheduleの最遅 departure が最善。移動・待機で時刻は増えるため、その候補はTを超えずmaxheapで確定した駅を後から改善できない。終点∞からの逆向きDijkstraが全合法routeの最遅開始を得る。

実装上の注意

  • T-c<lなら利用可能便なし。∞からの計算とl+(k-1)dは64bitで扱い、priority queueの古いentryをf値比較で捨てる。

復習の核

  • 最終便ちょうど接続、一本前しか間に合わない、乗換同時刻、cycleを含む路線、到達不能を便列挙可能な小例と比較する。

計算量と制約

時間

N駅、M schedule。各schedule定数時間算術とmaxheapで O((N+M)log N)。

空間

逆隣接と最新時刻、heap O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2\leq N\leq2\times10 ^ 5; 1\leq M\leq2\times10 ^ 5; 1\leq l _ i,d _ i,k _ i,c _ i\leq10 ^ 9\ (1\leq i\leq M); 1\leq A _ i,B _ i\leq N\ (1\leq i\leq M); A _ i\neq B _ i\ (1\leq i\leq M); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Last Train の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最短路モデル

主題
  • 最短路モデル: 非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 最短路モデル

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 最短路モデル

      • 非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。

      先に読む単元:

      • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題