第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)

5

高速道路の通行料金 (Highway Tolls)

Author : 渡邉 雄斗

共通の考察
通行料金の総和の最小値を求める上では，移動方法について以下の制約を加えても問題ありません（証明は省略しますが，後述の「小課題 4 以降に共通の考察」から自然と導かれます）．

• 高速道路を通行せずにどこかの都市に留まっている時間はないものとする．
• 都市 1 を出発する時刻は整数時刻とする．
なお，Li が整数であることから，以上の 2 つの制約が満たされるとき，任意の都市を出発する時刻が整数時刻になることに注意してください．

小課題 1
通行料金は時刻によらず一定なので，単純な最短経路問題になります．最短経路問題を解くアルゴリズム
としては Dijkstra 法，Bellman-Ford 法，Floyd-Warshall 法などがよく知られていますが，そのいずれを用いても解くことができます．

小課題 2
以下のような動的計画法を考えます．

dp[ j][t] : 時刻 t に都市 j にいるとき，ここから都市 N まで移動するのに必要な通行料金の総和の最小値
遷移としては都市 j から伸びている各高速道路の通行について考えればよく，現在の時刻 t を情報として持っているため，その通行料金は簡単に計算できます．
また，時刻 t としてありうる値は本来無限にありますが，正の時刻に都市 1 を出発するような経路や負の時刻に都市 N に到着するような経路を考える必要はない（＊）ため，t の絶対値は高々 N × max Li 程度としてしまってよいです．よって，計算量は O(N(N + M) × max Li ) です．

問題 5- 1 / 4

第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)（＊）の理由：正の時刻に都市 1 を出発する場合，代わりに時刻 0 に都市 1 を出発して全く同じ経路を辿っても通行料金の総和は増加しないため．負の時刻に都市 N に到着する場合についても同様．

小課題 3
経路は 1 通りに定まっているので，都市 1 を出発する時刻についてのみ考えればよいです．
都市 1 を出発してから都市 j に到着するまでの時間を S j (= L1 + L2 + · · · + L j−1 ) とおきます．都市 1 を出発する時刻を t とすると，通行料金の総和は
N−1
∑

N−1
∑

(Ci + K × |t + S i |) = K

i=1

N−1
∑

|t + S i | +i=1

N−1∑

Ci となるため，

i=1|t + S i | を最小化すればよいです．S 1 < S 2 < · · · < S N−1 に注意すると，この値は t = −S ⌊ N2 ⌋ のときに最i=1小値をとる（＊＊）ため，O(N) で答えを求めることができます．

（＊＊）の理由： f (t) =N−1∑

|t + S i | とおき，t′ = S ⌊ N2 ⌋ とします．このとき， f (t) は t ≦ t′ の範囲で単調減少

i=1

し t ≧ t′ の範囲で（広義）単調増加します（証明略）．よって， f (t) は t = t′ で最小値をとります．
なお，これは「数の集合 A = {A1 , A2 , . . . , Ak } が与えられたとき，関数 f (x) = |x − A1 | + |x − A2 | + · · · + |x − Ak |は x が A の中央値のとき最小値をとる」という事実としてよく知られているものです．

小課題 4 以降に共通の考察
小課題 3 の考察を用いると，経路を 1 つ決め打ったときの通行料金の総和の最小値を各道路の寄与に分解した形で表すことができます．例えば，道路 w, x, y, z をこの順に通行して都市 1 から都市 N まで移動するとき，前述の考察より時刻 −Lw に都市 1 を出発するのが最適ですから，通行料金の総和の最小値は(Cw + K ×|− Lw |)+(C x + K ×0)+(Cy + K ×|L x |)+(Cz + K ×|L x + Ly |) = (C x + KLw )+(C x +2KL x )+(Cy + KLy )+(Cz )となります．より一般に，通行料金の総和の最小値は通行する全ての道路に対する Ci + coef i × KLi の総和になります．ここで，係数 coef i は「通行する道路の数」と「その道路を何番目に通行するか」から定まる係数です．

小課題 4
通行する道路の数，およびそれぞれの道路についてその道路を通行する場合何番目に通行するかが一通りに定まります．よって，上述した各道路の寄与 Ci + coef i × KLi は経路に依存しないので，単純な最短経路問題になります．

問題 5- 2 / 4

第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)

小課題 5
通行する道路の数を固定してみます．このとき，各道路の寄与は「その道路を何番目に通行するか」にのみ依存しますから，今いる都市の情報に加えて今までに通行した道路の数の情報を付与した O(N 2 ) 頂点の拡張グラフ上では各道路の寄与が一意に定まり，単純な最短経路問題に帰着されます．通行する道路の数を全探索し，帰着された最短経路問題を解くのに dijkstra 法を用いることで，O(N 2 (N + M) log N) の計算量で解くことができます．

小課題 6
各経路の寄与を定める係数 coef i についてもう少し考察を進めてみましょう．
何らかの経路を定めたとき，前述の考察より，最適解においては時刻 0 ぴったりに訪れるような都市が必ず存在します．この都市を仮に a とおくと，以下の事実が観察できます．

• 都市 1 から都市 a に至るまでに通行する道路を通行順に並べたとき，それらの道路の係数は 1, 2, 3, . . .というようになっている．

• 都市 a から都市 N に至るまでに通行する道路を通行順と逆順に並べたとき，それらの道路の係数は0, 1, 2, . . . というようになっている．
時刻 0 ぴったりに訪れるような都市 a を 1 つ固定し，経路を「都市 1 から都市 a まで移動するパート」と「都市 N から都市 a まで高速道路を逆走して移動するパート」に分けて考えます．すると，上述の考察より，• 各 1 ≦ v ≦ N ，1 ≦ p ≦ N について，都市 1 から都市 v まで p 本の道路を通行して移動するのに必要な通行料金の総和の最小値• 各 1 ≦ v ≦ N ，1 ≦ p ≦ N について，都市 N から都市 v まで p 本の道路を逆走して移動するのに必要な通行料金の総和の最小値が小課題 5 と同様の dijkstra 法によって O(N(N + M) log N) で求まるので，それぞれのパートにおける必要な通行料金の総和の最小値が計算できます．これらの情報は a を変えるたびに再計算する必要はなく，最初に 1 度求めてしまえばよいものですから，a を全探索しても変わらず O(N(N + M) log N) の計算量で解くことができます．

満点「都市 1 から都市 v まで p 本の道路を通行して移動するのに必要な通行料金の総和の最小値」を dp[v][p]とおきましょう．この DP テーブルの各値は p の昇順に見ていけば単純な計算で求めることができ，最短経問題 5- 3 / 4

第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)

路問題に帰着して dijkstra 法を用いる必要は実はありません．「都市 N から都市 v まで p 本の道路を逆走して移動するのに必要な通行料金の総和の最小値」についても同様ですから，計算量は O(N(N + M)) になり，満点を獲得できます．

問題 5- 4 / 4