[1] 最適解の構造

まず、車両基地を併設する駅が昇順に \(i_0,i_1,\dots,i_k\) であるときの必要なコストの最小値について考えます。ここで、\(i_0 = 0, i_k = N\) です。

このとき、手順 \(2\) において列車を走らせる駅間としては \((i_{\ell},i_{\ell+1})~(0\leq \ell\leq k-1)\) のみを考えればいいです。というのは、\((i_{\ell},i_{r})\) 間に \(1\) 本列車を走らせるのと、\((i_{\ell},i_{\ell+1}),(i_{\ell+1},i_{\ell+2}), \ldots, (i_{r-1},i_r)\) 間にそれぞれ \(1\) 本ずつ列車を走らせるのでは、混雑度の減少分とコストがいずれも一致するからです。

以上の考察より、\((i_{\ell},i_{\ell+1})\) 間に列車を \(\max\lbrace C_{i_\ell},\dots,C_{i_{\ell+1}-1} \rbrace\) 本の列車を走らせるのが最適であることが言えます。従って、必要なコストの最小値は以下のようになります。

\[ \sum_{\ell=0}^{k}A_{i_\ell} + \sum_{\ell = 0}^{k-1} (i_{\ell+1}-i_{\ell})\times \max\lbrace C_{i_\ell},\dots,C_{i_{\ell+1}-1} \rbrace \]

ただし、便宜的に \(A_0 = A_N = 0\) としています。

---

[2] 動的計画法

以下の動的計画法を考えます。

\(\mathrm{dp(i)}\coloneqq\) 駅 \(i\) に車両基地を併設し、駅 \((0,1),(1,2),\ldots,(i-1,i)\) 間の混雑度を全て \(0\) 以下にするのに必要な最小のコスト

dp の初期化は \(\mathrm{dp}(0) = 0\) で、求めたい答えは \(\mathrm{dp}(N)\) です。 先の考察より、この dp は以下のように計算することができます。

\[ \mathrm{dp}(i) = \min\lbrace \mathrm{dp}(j) + (i-j)\times \max\lbrace C_j,\dots,C_{i-1}\rbrace \mid 0\leq j < i \rbrace + A_i \]

---

[3] 分割統治による高速化

dp を愚直に計算すると、計算量は \(\Theta(N^2)\) となってしまいます。そこで、分割統治を用いることで高速化を図ります。

アルゴリズムは以下の擬似コードのように記述できます。ここで、transition(l,m,r) は dp の \([\ell,m)\) から \([m,r)\) への遷移を計算する関数であり、solve(l,r) は \([0,\ell)\) での dp の値が確定しているときに、\([\ell,r)\) での dp の値を確定させる関数です。

def transition(l, m, r)
    for i = m to r - 1 do
        dp[i] = min(dp[i], min{dp[j] + (i - j) * max(c[j],...,c[i - 1]) | l <= j < m} + a[i])
    end for

def solve(l, r)
    if r = l + 1
        return
    end if

    m = floor((l + r) / 2)

    solve(l, m)
    transition(l, m, r)
    solve(m, r)

solve(0, N + 1)

この分割統治アルゴリズムにおいては、transition(l,m,r) を高速に実行できることが肝要となります。

---

[4] Convex Hull Trick を用いた遷移高速化

dp の遷移が一次関数の \(\min\) のような形になっていることに着目して Convex Hull Trick を用いることで、transition(l,m,r) を \(O(r-\ell)\) 時間で実行できます。これによって、アルゴリズム全体の計算量は \(O(N\log N)\) となります。

まず前準備として、\(j = \ell,\ldots,m-1\) と \(i = m,\ldots,r-1\) について以下の \(f(j),g(i)\) を計算します。

\[ f(j) = \max\lbrace C_j,\ldots,C_{m-1} \rbrace\\ g(i) = \max\lbrace C_{m-1},\ldots,C_{i-1} \rbrace \]

このとき、\(\mathrm{dp}(j)\) から \(\mathrm{dp}(i)\) への遷移は

\[ \mathrm{dp}(i) = \min\lbrace \mathrm{dp}(i),~\mathrm{dp}(j) + (i-j)\times \max\lbrace f(j),~g(i) \rbrace + A_i \rbrace \]

となります。\(\max\) を外すために、\(f(j)\geq g(i)\) なる \(j\) と \(f(j) < g(i)\) なる \(j\) に分けて遷移を考えます。ここで、\(f(j)\) は \(j\) について広義単調減少、\(g(i)\) は \(i\) について広義単調増加となることに注意します。

\(f(j)\geq g(i)\) である \(j\) から \(i\) への遷移

\(i\) を降順に見ていきます。このとき、\(g(i)\) は減少していくので \(f(j)\geq g(i)\) を満たす \(j\) の集合は大きくなっていきます。尺取り法の要領で \(f(j)\geq g(i)\) を満たす \(j\) について直線 \(y = f(j)\times x + \mathrm{dp}(j) - f(j)\times j\) を追加し、\(x = i\) での最小値に \(A_i\) を足した値を計算すればよいです。追加する直線の傾き、クエリの \(x\) 座標にいずれも単調性があるため、全ての \(i\) への遷移を \(O(r-\ell)\) 時間で計算できます。

\(f(j) < g(i)\) である \(j\) から \(i\) への遷移

\(i\) を昇順に見ていきます。このとき、\(g(i)\) は増加していくので \(f(j) < g(i)\) を満たす \(j\) の集合は大きくなっていきます。尺取り法の要領で \(f(j)\geq g(i)\) を満たす \(j\) について直線 \(y = -jx + \mathrm{dp}(j)\times j\) を追加し、\(x = f(i)\) での最小値に \(f(i)\times i + A_i\) を足した値を計算すればよいです。追加する直線の傾き、クエリの \(x\) 座標にいずれも単調性があるため、全ての \(i\) への遷移を \(O(r-\ell)\) 時間で計算できます。