ABC 422 F — Eat and Ride

考察

path上で頂点vを訪れた後に残りedge数がnなら、W_vは以後n回の燃料へ寄与しnW_vとなる。最適pathはcycleを除けるため長さはN-1以下である。最初にpath長d枚のticketを持ち、vertex uでn枚ならnW_uを払いedgeを渡ってn-1枚にする表現は、元の各W_uが残り全edgeで消費される総額と一致する。

採用する候補: (vertex,残りticket数)のlayered DAG DP

edge移動ごとにticketが1減るためacyclicで、全path長候補をO(NM)で同時に評価できる。

棄却する候補: 通常edge weightによる一回のDijkstra

edge costがそれまで訪れたvertex weight累積に依存し、現在vertexだけではMarkovな固定重みにならない。

全n=0..N-1のstate(1,n)をcost0にし、nを大から小へ処理する。元edgeu-vごとに(u,n)→(v,n-1) cost nW_uと逆向きをrelaxし、最終layer0の各vertex距離を出す。rolling layerでspaceを抑える。

典型の発動条件

時間展開DAG

発動条件: 遷移回数上限があり、step残数が必ず1減る。

vertex×remaining stepsへ展開して依存costを固定edge weightにする。

寄与の順序交換

発動条件: 累積weightをedgeごとに足す目的をvertexごとの残り回数寄与へ変える。

pathの二重和をW_v×後続edge数として数え直す。

問題固有の要素

開始ticket数を0…N-1全て許すことで、到達先ごとに最適path長を別に選べる。

別の問題へ持ち帰る視点: 可変長pathは全layerのsource初期化で一つのDAG shortest pathへ統合できる。

正当性

長さlの道の燃料はΣ_{j=0}^{l−1}(l−j)W_{v_j}へ順序を入れ替えられる。残りn辺の状態から一歩進む重みnW_vはこの式の一項である。全初期残歩数0..N−1からcost0で始めると各長さのpathを同一DPで比較できる。正の体重増分により閉路を削除すれば後の体重も辺数も減って燃料は増えないため最適は単純path、長さ≤N−1。従ってlayer0の最小が全最適を網羅する。

実装上の注意

  • 同じlayer内でedgeを連鎖させず必ずn→n-1へ遷移する。costは最大級なので64bitとINF guardを使う。

復習の核

  • path/cycle graphで全simple pathを列挙し、ticket DPと元costを比較する。

計算量と制約

時間

元 graph N頂点 M辺。残歩数 N層、各層 O(N+M) 更新で O(N(N+M))。

空間

rolling二層距離とgraphで O(N+M)、出力 N個。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\le N\le5000; 1\le M\le5000; 1\le W _ i\le10 ^ 9\ (1\le i\le N); 1\le u _ i\le v _ i\le N\ (1\le i\le M); The given graph is connected.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Eat and Ride の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小十分状態からDPを設計する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: DPの最小十分状態

    補助タグ: 寄与の数え上げと順序交換

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

    学習の位置

    体系上の位置: 最小十分状態からDPを設計する

    • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

    先に読む単元:

    • 局所寄与へ分解して集計順を交換する — 数える対象を一意に固定し、その対象を含む選択や組の個数へ集計順を交換する。要素・組・区間・値のどれを固定すると重複が消えるかを比較する。

    この解説で扱わないこと:

    • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題