この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
ワーシャルフロイド法について、以下の文献が参考になります。
- 最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ の「ワーシャル・フロイド法」
- プログラミングコンテストチャレンジブック (通称 蟻本) の「2-5 あれもこれも実は “グラフ”」
- ワーシャル・フロイド法での全点対最短経路を求めるアルゴリズム
60. GRL_1_C – 全点対間最短経路
全点対間最短経路の距離を求める問題であるため、ワーシャルフロイド法で解くことを検討します。
以下の文献にある通り、ワーシャルフロイド法は負の閉路の有無も判定できます。
- プログラミングコンテストチャレンジブック (通称 蟻本) の「2-5 あれもこれも実は “グラフ”」
- ワーシャル・フロイド法での全点対最短経路を求めるアルゴリズム の「負の閉路の検出」
\mathrm{cost}[i][j] を頂点 i から頂点 j への最短経路の距離とします。
i = j は閉路を表すため \mathrm{cost}[i][j] は 0 で初期化します。その他の \mathrm{cost}[i][j] は正の閉路無しでは実現できない大きな値で初期化します。|V| \leq 100, d_i \leq 2 \times 10^7 のため、例えば 2 \times 10^9 で初期化します。
ワーシャルフロイド法の更新の際、頂点 k を使う場合の候補は i から k への経路と k から j への経路がともに存在するときのみ計算し、\mathrm{cost}[i][j] と比較するようにします。こうすることで辺の重みが負になりうる場合でも、(実現不可能な) 初期値との比較により経路の有無を判定できます。
計算量は O(|V|^3) = 10^6 程度です。
61. AtCoder Beginner Contest 012 D – バスと避けられない運命
問題を以下の 2 つの問題に分解します。
- 各バス停の対に対し、バスに乗る時間の最小値を求めなさい。
- 各バス停の対 (i, j) の乗車時間 \mathrm{cost}[i][j] が与えられます。\min_i \max_j \mathrm{cost}[i][j] を求めなさい。
1 はワーシャルフロイト法で求められます。
2 は N \leq 300 のため、O(N^2) = 10^5 程度の全探索で求められます。
t_i \geq 1 であるため、同じバス停の対の乗車時間は 0, それ以外の対の乗車時間は十分大きな値で初期化すると条件分岐を減らせます。N \leq 300, t_i \leq 1000 のため、例えば 10^6 で初期化します。
全体の計算量は O(N^3) = 10^8 程度です。
62. AtCoder Beginner Contest 079 D – Wall
入力例 1 と出力例 1 にあるように数字 i を数字 j に書き変える魔力の最小値は c_{ij} とは限りません。他の数字を経由して書き変えた方が少ない魔力で書き変えられる場合があります。
そこで問題を以下の 2 つに分解します。
- すべての一桁の数字 i, j に対し、i を j に書き変える際に必要な魔力の最小値を求めなさい。
- 数字 i を数字 j に書き変える際に必要な魔力の最小値が与えられます。壁に書かれている数字をすべて 1 にする際に必要な魔力の最小値を求めなさい。
1 は数字を点、c_{i,j} を辺 (i,j) の重みとするグラフに対し、ワーシャルフロイト法で求められます。
2 はマス目を全探索し、各マスの数字を 1 にするために必要な魔力を合計すれば求められます。
計算量は 1 は 10^3 程度、2 は O(HW) = 10^5 程度です。
63. AtCoder Beginner Contest 074 D – Restoring Road Network
任意の都市の対 (u, v) に対し、u から v への最短距離が A_{u,v} であるとき、以下が成立します。
- 任意の w に対し、A_{u, v} \leq A_{u, w} + A_{w, v}
もし、A_{u, v} > A_{u, w} + A_{w, v} となる w が存在するとき、u から w を経由して v へ移動した方が距離が短くなるため、A_{u, v} が最短距離であることに矛盾します。
逆に任意の u, v, w に対し、A_{u, v} \leq A_{u, w} + A_{w, v} が成立する場合、都市 u と都市 v の間に長さ A_{u, v} の道路が存在する構造を考えると、この構造は条件を満たす構造になります。
次に、構造が存在するとして道路の和が最小になる構造について検討します。各 A_{u, v} について以下のいずれかが成立します。
場合 1 任意の w (\neq u, v) に対し A_{u, v}<A_{u, w} + A_{w, v}
場合 2 A_{u, v} = A_{u, w} + A_{w, v} となる w (\neq u, v) が存在する。
1 が成立するとき、u と v の間には長さ A_{u, v} の道路が必要です。もし、他の都市 w を経由する距離 A_{u, v} が存在する場合、u から w への距離、w から v への距離のいずれかが A_{u, w}, A_{w, v} より真に短くなります。これは任意の u, v に対し、A_{u, v} が最短経路の長さであることに矛盾します。
よって、条件を満たす任意の構造 (道路の集合) には 1 が成立する u と v の間の長さ A_{u, v} の道路が属します。
逆に 1 が成立する都市の対 (u, v) の間にのみ長さ A_{u, v} の道路が存在する構造を考えます。任意の u, v \ (u \neq v) に対し A_{u, v} \geq 1 であるため、2 が成立する A_{u, v} は有限回の操作で以下のように変形できます。
A_{u, v} = \sum_{i = 1}^{n} A_{w_{i – 1}, w_{i}}
\{w_i\}_{i=0}^{n} は以下を満たす都市の列です。
- もし i \neq j ならば w_i \neq w_j
- 都市 w_{0} は u であり、都市 w_{n} は v である。
- 任意の i, t に対し A_{w_{i-1}, w_i} \lt A_{w_{i-1}, t} + A_{t, w_i}
1 が成立する都市の対 (u, v) の間に長さ A_{u, v} の道路が存在するため、(w_{i-1}, w_i) の間には道路があります。そのため、u, w_1, w_2, \dots, w_{n-1}, v の順に道路を通ることができ、このときの u, v の距離は A_{u, v} になります。
よって任意の頂点の対 (u, v) について最短距離 A_{u, v} を実現する道路の組み合わせが存在するため、この構造は条件を満たす構造です。
以上から、1 が成立する u, v の A_{u,v} の和が計算すべき最小値になります。
道路の構造の有無の判定も計算すべき最小値もワーシャルフロイド法と似た 3 重ループで計算できます。
計算量は N \leq 300 の 3 重ループがあるため、O(N^3) = 10^8 程度です。
