ABC 232 G — Modulo Shortest Path

考察

辺 i→j の重み (A_i+B_j) mod M は、円周 0,…,M−1 上で座標 (−A_i) mod M から B_j まで正方向へ進む距離である。各元頂点は一つの出発座標へ重み 0 で入り、一つの到着座標から重み 0 で出られると考えると、N² 本の辺を共通の円周移動へまとめられる。円周上で途中に必要座標を挟んでも距離の和は変わらないため、全 M 座標を作らずソート済みの必要座標間だけを結べばよい。

棄却する候補: 完全有向グラフの全 N(N−1) 辺を生成してダイクストラ法を行う。

頂点対ごとの辺数と走査時間が二乗規模になり、N=20 万では保持できない。

採用する候補: 必要な (−A_i) mod M と B_i だけを円周座標ノードとして圧縮し、隣接座標間の時計回り辺と元頂点への 0 辺から疎な等価グラフを作る。

任意の元辺の重みを円周上の経路長として再現でき、座標ノードと辺は入力数に比例する。

加法 mod M の完全グラフ辺を円周距離へ因数分解し、座標圧縮した循環補助グラフ上の通常の非負最短路としてダイクストラ法を適用する。

典型の発動条件

密グラフの補助頂点による疎化

発動条件: 全点対の辺重みが出発側パラメータと到着側パラメータを共有構造上で合成して表せるとき。

元頂点を円周上の入口・出口座標へ接続し、共通の座標間移動辺を全ペアで共有する。

循環座標圧縮

発動条件: 巨大な剰余環上を単調に進むが、立ち寄る必要がある座標は入力由来の少数だけのとき。

必要座標をソート・重複除去し、各座標から次座標へ剰余差を重みにした循環辺を張る。

問題固有の要素

(A_i+B_j) mod M の始点を A_i ではなく −A_i と置くことで、式が円周上の前進距離そのものになる。

別の問題へ持ち帰る視点: mod を含む二項式の重みは、一方を符号反転した円周座標間距離として表せないか試す。

正当性

元辺costは出発座標−A_iから到着B_jへの正方向円周距離。この移動を隣接圧縮座標の差分辺で分解するとcostが一致する。元→出発、到着→元の0辺で元pathを再現し、逆に補助pathの円周区間を元辺へ畳めるので最短距離を保つ。

実装上の注意

  • 同じ剰余座標は一ノードへ統合し、最後の座標から最初への辺重みも (first−last) mod M として張る。
  • 元問題は i≠j だが補助グラフには自己へ戻る経路も生じる。重みが非負なので自己周回は最短距離を改善せず、異頂点間の距離を変えない。

復習の核

  • N² 辺でも重み式が出発項+到着項なら、共有できる中間状態を作って辺を経路へ分解する。
  • 剰余差の補助グラフでは、最大座標から最小座標への wrap-around 辺を忘れず円周を閉じる。

計算量と制約

時間

元N頂点、相異なる円周座標V≤2N。sort O(N log N)、補助graph Dijkstra O(N log N)。

空間

元点と圧縮座標、O(N)辺で O(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 2 \leq M \leq 10^9; 0 \leq A_i, B_j < M; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Modulo Shortest Path の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

    主タグ: 最短路モデル

    補助タグ: 座標・値の順序保存圧縮

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

    学習の位置

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

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

    先に読む単元:

    • 疎なkeyの順序を保ってdense indexへ圧縮する — 保持すべき疎な座標をsort-uniqueして順序・等値性を添字へ写す。距離・時間差・区間長も使う場合は元座標と間隔を併せて保存する。
    • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題