頂点数が \(N\) 個で、\(t = 1, 2, \ldots, T\) について頂点 \(u_t\) から頂点 \(v_t\) への重み \(t\) の辺を持つ（その他に辺はない）有向グラフ \(G\) を考えます。

このとき、「時刻 \(t\) において頂点 \(v\) が良い頂点である」ことは、「 \(G\) で頂点 \(1\) から重み \(t\) 以下の辺のみをちょうど \(L\) 回たどって頂点 \(v\) に到達できる」ことと同値です。

したがって本問題の \(v = 1, 2, \ldots, N\) についての答えは、下記の問題の \(v = 1, 2, \ldots, N\) についての答えとそれぞれ等しいです。

\(G\) で頂点 \(1\) から頂点 \(v\) までちょうど \(L\) 回の移動で到達するときの「通る辺の重みの最大値」としてあり得る最小値を求めよ。

動的計画法(DP)でこの問題を解きます。

\(i = 0, 1, 2, \ldots, L\) および \(j = 1, 2, \ldots, N\) について、\(\mathrm{dp}[i][j]\) を

\(\mathrm{dp}[i][v] := \) (ちょうど \(i\) 回の移動によって頂点 \(v\) に到達するときの「通る辺の重みの最大値」としてあり得る最小値)

とおきます。ただし、ちょうど \(i\) 回の移動によって頂点 \(v\) に到達することが不可能な場合は \(\mathrm{dp}[i][v] = \infty\) とします。

DPの初期状態を考えます。\(v = 2, 3, \ldots, N\) については、\(\mathrm{dp}[\ast][\ast]\) の定義より

\[\mathrm{dp}[0][v] = \infty\]

です。

また、便宜上

\[\mathrm{dp}[0][1] = 0\]

とします。

次にDPの遷移を述べます。 \(1 \leq i, j \leq N\) に対して、\(W(i, j)\) を「 \(G\) 上での頂点 \(i\) から頂点 \(j\) への有向辺の重み」とします。ただし、そのような有向辺が存在しない場合は \(W(i, j) := \infty\) とします。

このとき、DPの遷移式は

\[ \begin{aligned} \mathrm{dp}[i][v] &= \displaystyle\min_{1 \leq u \leq N} \max \lbrace \mathrm{dp}[i-1][u], W(u, v) \rbrace\\ &= \min\lbrace \max\lbrace \mathrm{dp}[i-1][1] , W(1, v)\rbrace, \max\lbrace \mathrm{dp}[i-1][2] , W(2, v)\rbrace, \ldots, \max\lbrace \mathrm{dp}[i-1][N] , W(N, v)\rbrace \rbrace \end{aligned} \]

と書けます。

上記の初期化と遷移によって、\(\mathrm{dp}[i][\ast]\) を \(i = 1, 2, \ldots, L\) の順に計算することで、本問題の答えが

\[\mathrm{dp}[L][1], \mathrm{dp}[L][2], \ldots, \mathrm{dp}[L][N]\]

として得られます。

しかしこの方法は、\(NL\) 通りの \((i, j)\) について \(\mathrm{dp}[i][j]\) の値を計算するため、実行制限時間に間に合いません。 よって、以下でこの方法を高速化する方法を述べます。

上述のDPの遷移式：

\[ \begin{aligned} \mathrm{dp}[i][v] &= \displaystyle\min_{1 \leq u \leq N} \max \lbrace \mathrm{dp}[i-1][u], W(u, v) \rbrace\\ &= \min\lbrace \max\lbrace \mathrm{dp}[i-1][1] , W(1, v)\rbrace, \max\lbrace \mathrm{dp}[i-1][2] , W(2, v)\rbrace, \ldots, \max\lbrace \mathrm{dp}[i-1][N] , W(N, v)\rbrace \rbrace \end{aligned} \]

で、\(\max \lbrace a, b\rbrace\) を掛け算 \(a \cdot b\) に、\(\min \lbrace a, b \rbrace\) を足し算 \(a + b\) に置き換えると、

\[\begin{aligned} \mathrm{dp}[i][v] &= \displaystyle\sum_{u = 1}^N (\mathrm{dp}[i-1][u] \cdot W(u, v))\\ &= \mathrm{dp}[i-1][1]\cdot W(1, v) + \mathrm{dp}[i-1][2]\cdot W(2, v)+ \cdots + \mathrm{dp}[i-1][N]\cdot W(N, v) \end{aligned} \]

となり、これは行列を用いて

\[\left[\begin{matrix} \mathrm{dp}[i][1] \\ \mathrm{dp}[i][2] \\\vdots \\ \mathrm{dp}[i][N]\end{matrix}\right] = \left[ \begin{matrix} W(1, 1)& W(2, 1) & \cdots & W(N, 1) \\ W(1, 2) & W(2, 2) & \cdots & W(N, 2) \\ \vdots & \vdots & \ddots & \vdots\\ W(1, N) & W(2, N) & \cdots & W(N, N) \\ \end{matrix}\right] \left[\begin{matrix} \mathrm{dp}[i-1][1] \\ \mathrm{dp}[i-1][2] \\\vdots \\\mathrm{dp}[i-1][N]\end{matrix}\right] \]

と形式的に書けます。つまり、

\[\mathbf{A} := \left[\begin{matrix} W(1, 1)& W(2, 1) & \cdots & W(N, 1) \\ W(1, 2) & W(2, 2) & \cdots & W(N, 2) \\ \vdots & \vdots & \ddots & \vdots\\ W(1, N) & W(2, N) & \cdots & W(N, N) \\ \end{matrix}\right]\]

とし、\(i = 0, 1, 2, \ldots, L\) について

\[\mathbf{x}_i := \left[\begin{matrix} \mathrm{dp}[i][1] \\ \mathrm{dp}[i][2] \\\vdots \\\mathrm{dp}[i][N]\end{matrix}\right]\]

とおくと、\( i= 1, 2, \ldots, L\) について、

\[\mathbf{x}_i = \mathbf{A} \mathbf{x}_{i-1}\]

です。ただし、乗法は \(\max\) 、加法は \(\min\) として計算することに注意してください。

本問題の答えである \(\mathrm{dp}[L][1], \mathrm{dp}[L][2], \ldots, \mathrm{dp}[L][N]\) を求めるには、 \(\mathbf{x}_L\) を求めれば良いですが、これは

\[\mathbf{x}_L = \underbrace{\mathbf{A} (\mathbf{A} (\mathbf{A} (\ldots( \mathbf{A}}_L \mathbf{x}_0) \ldots)))\]

と書けます。 一般に、乗法を \(\max\) 、加法を \(\min\) としても、行列の乗法に関する結合法則

\[(\mathbf{P}\mathbf{Q})\mathbf{R} = \mathbf{P}(\mathbf{Q}\mathbf{R})\]

が成り立ちます。よって、

\[\mathbf{x}_L = \underbrace{\mathbf{A} (\mathbf{A} (\mathbf{A} (\ldots \mathbf{A}( \mathbf{A}}_L \mathbf{x}_0) \ldots))) = (\mathbf{A}^L)\mathbf{x}_0\]

と書けます。 したがって、乗法を \(\max\) 、加法を \(\min\) として、\(\mathbf{A}^L\) を繰り返し二乗法によって計算することで、本問題を \(\mathrm{O}(T+N^3 \log L)\) 時間で解くことができます。

おまけ

一般に、加法と乗法が半環をなすとき、行列の乗法に関する結合法則が成り立ち、上述のような行列の累乗によるDPの高速化が可能です。

半環とは、加法 \(+\) と乗法 \(\cdot\) という \(2\) つの二項演算を備えた集合 \(A\) であって、下記をすべて満たすものです。

• \((A, +)\) は可換モノイドをなす。すなわち、次の \(3\) 点を満たす。

  • \(+\) に関する結合法則が成り立つ。すなわち、任意の \(a, b, c \in A\) に対して、\((a+b)+c = a+(b+c)\) が成り立つ。
  • \(+\) に関する単位元 \(0\) が存在する。すなわち、ある \(0 \in A\) が存在して、任意の \(a \in A\) に対して、\(a + 0 = 0+ a = a\) が成り立つ。
  • \(+\) に関する交換法則が成り立つ。すなわち、任意の \(a, b \in A\) に対して、\(a + b = b + a\) が成り立つ。

• \((A, \cdot)\) はモノイドをなす。すなわち、次の \(2\) 点を満たす。

  • \(\cdot\) に関する結合法則が成り立つ。すなわち、任意の \(a, b, c \in A\) に対して、\((a\cdot b)\cdot c = a\cdot(b\cdot c)\) が成り立つ。
  • \(\cdot\) に関する単位元 \(1\) が存在する。すなわち、ある \(1 \in A\) が存在して、任意の \(a \in A\)に対して、\(a \cdot 1 = 1\cdot a = a\) が成り立つ。

• \(+\) と \(\cdot\) に関して、次の分配法則が成り立つ。

  • 任意の \(a, b, c \in A\) に対して、\(a \cdot (b + c) = a \cdot b + a \cdot c\) が成り立つ。
  • 任意の \(a, b, c \in A\) に対して、\((a+b) \cdot c = a \cdot c + b \cdot c\) が成り立つ。

• 任意の \(a \in A\) に対して、\(0 \cdot a = a \cdot 0 = 0\) が成り立つ。

例えば、

• \(A := \R \cup \lbrace -\infty \rbrace\)、加法 \(+\) を \(\max\) 、乗法 \(\cdot\) を通常の加算
• \(n\) を正の整数とし、\(A\) を \(2^n\) 未満の非負整数の集合、加法 \(+\) をビットごとの論理和、乗法 \(\cdot\) をビットごとの論理積
• \(n\) を正の整数とし、\(A\) を \(2^n\) 未満の非負整数の集合、加法 \(+\) をビットごとの排他的論理和、乗法 \(\cdot\) をビットごとの論理積

とすると、それぞれ半環をなします。