概要

大雨で陥没した一本道の各区画を、隣接する区画との高さの差がすべて \(D\) 以下になるように、最小のコストでかさ上げする問題です。

各区画の最適な最終的な高さは、他の区画の初期の高さから一意に決定されるため、累積最大値を用いることで \(O(N)\) の時間計算量で効率的に解くことができます。

考察

1. 最終的な高さの条件

すべての隣接する区画の高さの差を \(D\) 以下にするという条件は、任意の \(2\) つの区画 \(i, j\) について、以下の関係が成り立つことと同値です。 $\(|A'_i - A'_j| \leq |i - j| \times D\)$

また、道路を削る（高さを減少させる）ことはできないため、すべての \(i\) について \(A'_i \geq A_i\) である必要があります。

これらを組み合わせると、任意の区画 \(j\) の初期の高さ \(A_j\) に対して、区画 \(i\) の最終的な高さ \(A'_i\) は以下の条件を満たさなければなりません。 $\(A'_i \geq A_j - |i - j| \times D\)$

この式はすべての \(j\) （\(1 \leq j \leq N\)）について成り立つ必要があるため、区画 \(i\) の最終的な高さの下限値は以下のようになります。 $\(A'_i \geq \max_{1 \leq j \leq N} (A_j - |i - j| \times D)\)$

2. 下限値の妥当性

すべての \(i\) について、上記の「下限値そのもの」を最終的な高さ \(A'_i\) として設定したとき、問題の条件をすべて満たすでしょうか？ 実は、 \(A'_i = \max_{j} (A_j - |i - j| \times D)\) とおくと、以下の \(2\) つが成り立ちます。

1. 初期状態以上であること: \(j = i\) のとき \(A_j - |i - j| \times D = A_i\) となるため、 \(A'_i \geq A_i\) が必ず成り立ちます。
2. 隣接する差が \(D\) 以下であること: 三角不等式 \(|i - j| - 1 \leq |i + 1 - j| \leq |i - j| + 1\) より、任意の \(j\) について以下が成り立ちます。 $\(A_j - |i + 1 - j| \times D \leq A_j - (|i - j| - 1) \times D = (A_j - |i - j| \times D) + D \leq A'_i + D\)\( すべての \)j\( についての最大値を取ることで \)A’_{i+1} \leq A’_i + D\( が得られます。同様に \)A’i \leq A’{i+1} + D\( も示せるため、隣接する高さの差は必ず \)D$ 以下になります。

コスト \(C_i\) はすべて正（\(1 \leq C_i\)）であるため、コストを最小化するためには、各区画の高さをこの必要最小限の値 \(A'_i\) にぴったり一致させるのが最適です。

3. 高速化のための式変形

素直に各 \(i\) に対してすべての \(j\) を探索すると \(O(N^2)\) の時間がかかり、 \(N \le 10^6\) では実行時間制限（TLE）になってしまいます。そこで、絶対値を外して式を整理します。

• \(j \leq i\)（自分より左側）のとき: $\(A_j - |i - j| \times D = A_j - (i - j) \times D = (A_j + j \times D) - i \times D\)$
• \(j \geq i\)（自分より右側）のとき: $\(A_j - |i - j| \times D = A_j - (j - i) \times D = (A_j - j \times D) + i \times D\)$

このように式変形すると、最大値を求める部分を \(i\) に依存する項と \(j\) に依存する項に分離することができます。

アルゴリズム

0-indexed（\(0\) から \(N-1\) までの添字）で考えます。

1. 左側からの累積最大値の計算: すべての \(i\) について、 \(L_i = \max_{0 \leq j \leq i} (A_j + j \times D)\) を計算します。 これは、左から順に走査しながら cur = max(cur, A[i] + i * D) と更新していくことで、全体で \(O(N)\) で求められます。

2. 右側からの累積最大値の計算とコストの算出: すべての \(i\) について、 \(R_i = \max_{i \leq j \leq N-1} (A_j - j \times D)\) を計算します。 これは、右から順に走査しながら cur = max(cur, A[i] - i * D) と更新していくことで、全体で \(O(N)\) で求められます。

3. 目標の高さとコストの計算: 各区画 \(i\) の最適な高さ \(A'_i\) は以下のように求まります。 $\(A'_i = \max(L_i - i \times D, R_i + i \times D)\)\( 必要なコストは \)(A’_i - A_i) \times C_i$ となり、これをすべての区画について足し合わせたものが答えになります。

計算量

• 時間計算量: \(O(N)\) 左からの走査と右からの走査をそれぞれ \(1\) 回ずつ行うだけなので、 \(N = 10^6\) でも 0.1 秒未満で非常に高速に動作します。
• 空間計算量: \(O(N)\) 左からの累積最大値を記録する配列 \(L\) などを保持するために \(O(N)\) のメモリを使用します（右からの累積最大値 \(R\) は変数で保持しながら同時に答えを計算できるため、配列を分ける必要はありません）。

実装のポイント

• 大きな値の初期化: 累積最大値を求める際の初期値（cur）は、十分に小さな値（-10**18 など）で初期化してください。

• 高速な入出力: Python で \(N = 10^6\) の入力を扱う際は、 sys.stdin.read を用いて一括で入力を取得することで、入出力によるオーバーヘッドを減らすことができます。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    D = int(data[1])

    A = [int(x) for x in data[2 : 2 + N]]
    C = [int(x) for x in data[2 + N : 2 + 2 * N]]

    # L[i] = max_{j <= i} (A[j] + j * D)
    L = [0] * N
    cur = -10**18
    for i in range(N):
        val = A[i] + i * D
        if val > cur:
            cur = val
        L[i] = cur

    # R[i] = max_{j >= i} (A[j] - j * D)
    # 同時に、目標の高さ target = max(L[i] - i * D, R[i] + i * D) を求めてコストを計算する
    ans = 0
    cur = -10**18
    for i in range(N - 1, -1, -1):
        val = A[i] - i * D
        if val > cur:
            cur = val
        target = L[i] - i * D
        r_val = cur + i * D
        if r_val > target:
            target = r_val
        ans += (target - A[i]) * C[i]

    print(ans)


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-high によって生成されました。