ABC 286 E — Souvenir

考察

最優先はflight本数の最小化であり、その同率解の間だけsouvenir価値を最大化するので、経路評価は(distance, value)の辞書式順序になる。最短pathは同じ都市を繰り返さないため、頂点価値は出発都市を一度加え、edge u→vを通るたび到着都市A_vを加える形へ移せる。候補は距離が小さければ常に優先し、距離が等しいときだけ価値が大きい方へ更新すれば、問題の二段階最適化と一致する。i→kとk→jを連結すると都市kの価値を二重に数えるため、価値はval[i][k]+val[k][j]-A_kで合成する。

採用する候補: 全点対Floyd–Warshallの値を最短距離と同距離での最大価値のpairに拡張する。

N≤300で全queryを一括前計算でき、距離優先・価値優先の更新規則を厳密に実装できる。

棄却する候補: 各edge costを1-εA_vとする浮動小数最短路。

概念上は優先順位を埋め込めても、εと丸め誤差によりflight本数と価値の比較が壊れ得る。

棄却する候補: flight本数だけの最短距離を求めた後、任意の到達pathから価値を集計する。

同じ最短距離を持つ複数pathから最大価値のものを選ぶ情報が失われる。

dist[i][i]=0,val[i][i]=A_i、direct flight i→jにはdist=1,val=A_i+A_jを設定し、他は到達不能とする。各k,i,jで到達可能なら候補(distance=dist[i][k]+dist[k][j], value=val[i][k]+val[k][j]-A_k)を作り、distance最小・同率value最大で更新する。queryは到達不能ならImpossible、そうでなければpairを出力する。

典型の発動条件

多目的最短路の辞書式pair

発動条件: 最優先costを最適化し、その同率解でsecondary scoreを最適化するとき。

比較演算を距離昇順・価値降順に定義してrelaxする。

Floyd–Warshallの半環拡張

発動条件: 全点対queryが多く、path情報を結合可能な値として持てるとき。

pairの選択と中継点での結合を定義して三重loopを適用する。

問題固有の要素

都市価値をedge到着時の加点へ変換すると、出発点だけを初期値に持たせればpathの各都市を一度ずつ数えられる。

別の問題へ持ち帰る視点: 頂点重み付きpathは、開始点の初期寄与と入辺通過時の到着点寄与へ分解すると標準的な最短路更新へ載せやすい。

正当性

path比較は辺数最小、その中で価値最大の辞書順で、共通中継kの価値を一回引いて合成する。正の辺数により同距離候補は余計なcycleを含まずFloydの中継prefix不変条件が成立する。各段で最良pairを保持し全最短path最大価値を得る。

実装上の注意

  • 到達不能なpairを加算せず、価値総和は最大約300×10^9なので64bit整数を使う。
  • 中継合成ではA_kを一度引き、direct edgeの両端価値や始点価値を欠落・二重計上しない。

復習の核

  • 同じ2-edge距離で価値だけ異なる2経路を作って更新順を確認し、i→k→jのkが一度だけ加算されることとImpossible判定を照合する。

計算量と制約

時間

N都市、Q質問。pair最適Floyd O(N³)、照会O(Q)。

空間

距離と価値二行列 O(N²)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 300; 1\leq A_i\leq 10^9; S_i is a string of length N consisting of Y and N.; The i-th character of S_i is N.; 1\leq Q\leq N(N-1); 1\leq U_i,V_i\leq N; U_i\neq V_i; If i \neq j, then (U_i,V_i)\neq (U_j,V_J).; N,A_i,Q,U_i, and V_i are all integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

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

主題
  • 最短路モデル: 許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 最短路モデル

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

      学習の位置

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

      • 許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。

      先に読む単元:

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題