概要

各区画の高さを増やす（減らせない）操作によって、隣接区画の高さの差の絶対値をすべて \(D\) 以下にするための最小コストを求める問題です。各区画が最終的に取るべき「最小の高さ」を求め、そこまで上げるコストを合計すれば答えになります。

考察

重要な観察：各区画には「最終的にこの高さ以上でなければならない」という下限が存在する

まず、高さは減らせないので、最終的な高さ \(A_i'\) は必ず \(A_i' \geq A_i\) を満たします。

さらに、隣接区画の差が \(D\) 以下という制約から、ある区画 \(j\) の高さが \(A_j\) であるなら、そこから距離 \(|i-j|\) だけ離れた区画 \(i\) は少なくとも

\[A_i' \geq A_j - D \cdot |i-j|\]

を満たさなければなりません（隣に移るたびに最大 \(D\) ずつしか下げられないため）。

これがすべての \(j\) について成り立つ必要があるので、区画 \(i\) の高さの下限は

\[h_i = \max_{1 \leq j \leq N} \bigl(A_j - D \cdot |i-j|\bigr)\]

となります（\(j=i\) の項が \(A_i\) なので、自然に \(h_i \geq A_i\) も満たされます）。

この下限 \(h_i\) 自体が実現可能な解になっている

実は \(h_i\) をそのまま最終高さに採用すると、隣接する区画同士で \(|h_i - h_{i+1}| \leq D\) が成り立ちます（各 \(A_j - D|i-j|\) という項が隣接間で高々 \(D\) しか変化しないため、その最大値も同様）。

つまり \(h_i\) は「すべての制約を満たす最小の高さ」を各区画について同時に達成している 各座標ごとの最小解 です。任意の実現可能解は \(A_i' \geq h_i\) を満たすので、コスト \(C_i > 0\) が正であることから、すべての区画を \(h_i\) ちょうどに設定するのが最小コストになります。

よって答えは

\[\sum_{i=1}^{N} C_i \cdot (h_i - A_i)\]

素朴なアプローチの問題点

\(h_i\) を定義通り「各 \(i\) についてすべての \(j\) を調べる」と \(O(N^2)\) かかり、\(N \leq 10^6\) では間に合いません。工夫が必要です。

アルゴリズム

\(h_i = \max_j (A_j - D|i-j|)\) を、絶対値を左右に分けて 前方・後方の 2 回の走査 で計算します。

• 左側からの寄与（\(j \leq i\)）：\(A_j - D(i-j)\) の最大値を $\(L_i = \max(A_i,\ L_{i-1} - D)\)\( という漸化式で左から順に計算できます。1 つ右へ進むと過去の候補はすべて \)D$ ずつ小さくなるためです。

• 右側からの寄与（\(j \geq i\)）：同様に $\(R_i = \max(A_i,\ R_{i+1} - D)\)$ を右から計算します。

• 最終的に \(h_i = \max(L_i, R_i)\) とすれば、\(O(N)\) で全区画の下限が求まります。

コードでは前方走査で h[i] に \(L_i\) を入れ、後方走査で \(R_i\) を計算しながら h[i] と大きい方を取る、という形で 2 パスを実現しています。

具体例：\(A = [5, 0, 0, 3]\), \(D = 2\) の場合

• 前方走査：\(L = [5, 3, 1, 3]\)
• 後方走査：\(R = [5, 1, 3, 3]\)
• \(h = \max(L, R) = [5, 3, 3, 3]\)

たとえば区画 2 は、区画 1 の高さ \(5\) から \(D=2\) 下げても \(3\) までしか下げられないので \(h_2 = 3\) となっています。増やすコストは \(\sum C_i(h_i - A_i)\) で計算されます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• \(A_i, C_i\) が大きく、\(N\) も大きいため、答えは 64bit 整数の範囲になり得ます。Python では自動的に多倍長整数になるので問題ありませんが、C++ 等では long long を使う必要があります。

• \(N = 10^6\) と大きいので、入力は sys.stdin.buffer.read() で一括読み込みして高速化しています。

• 前方走査の値を h に保持しておき、後方走査で max を取りながら上書きすることで、余分な配列を増やさず 2 パスで完結させています。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    D = int(data[idx]); idx += 1
    A = [int(x) for x in data[idx:idx+N]]; idx += N
    C = [int(x) for x in data[idx:idx+N]]; idx += N

    # h_i = max_j (A_j - D*|i-j|)  via forward and backward passes
    h = A[:]

    # forward pass
    prev = A[0]
    for i in range(1, N):
        v = prev - D
        ai = A[i]
        cur = ai if ai > v else v
        h[i] = cur
        prev = cur

    # backward pass, combine with h (take max)
    prev = A[N-1]
    # last element: forward value already A[N-1] effectively, but ensure
    if A[N-1] > h[N-1]:
        h[N-1] = A[N-1]
    for i in range(N-2, -1, -1):
        v = prev - D
        ai = A[i]
        b = ai if ai > v else v
        prev = b
        if b > h[i]:
            h[i] = b

    ans = 0
    for i in range(N):
        ans += C[i] * (h[i] - A[i])
    sys.stdout.write(str(ans) + "\n")

main()

---

この解説は claude4.8opus-high によって生成されました。