概要

隣り合う区画の高さの差が \(D\) 以下になるように、各区画の高さを必要最小限だけ上げる問題です。

重要なのは、各区画の最終的な高さは「周囲の高い区画から強制される最低高さ」として一意に決まる、という点です。

考察

最終的な高さを \(B_i\) とします。

条件より、隣り合う区画の高さの差は \(D\) 以下なので、任意の区画 \(i, j\) について

\[ B_i \geq B_j - D|i-j| \]

が成り立ちます。

また、操作では高さを下げることはできないため、

\[ B_j \geq A_j \]

です。

したがって、

\[ B_i \geq A_j - D|i-j| \]

がすべての \(j\) について成り立ちます。

つまり、区画 \(i\) の最終的な高さは少なくとも

\[ \max_j (A_j - D|i-j|) \]

でなければなりません。

この値を \(H_i\) とすると、

\[ H_i = \max_j (A_j - D|i-j|) \]

です。

これは「各区画 \(j\) の元の高さ \(A_j\) が、距離 \(1\) 離れるごとに最大 \(D\) ずつしか下がれない」と考えたときに、区画 \(i\) に要求される最低高さです。

例えば、高さ \(10\) の区画があると、隣は最低でも \(10-D\)、その隣は最低でも \(10-2D\)、というように周囲に制約を与えます。

なぜこれが最適か

すべての \(C_i\) は正なので、必要以上に高さを上げると必ずコストが増えます。

また、ある区画を余分に高くしても、他の区画を低くできるわけではありません。むしろ新たな制約を生むだけです。

したがって、各区画を可能な限り低い高さ \(H_i\) にするのが最適です。

素朴な方法では難しい理由

各区画 \(i\) について、すべての区画 \(j\) を調べて

\[ \max_j (A_j - D|i-j|) \]

を計算すると、計算量は \(O(N^2)\) になります。

\(N \leq 10^6\) なので、これは到底間に合いません。

そこで、左側からの影響と右側からの影響を分けて、線形時間で計算します。

アルゴリズム

区画 \(i\) に必要な高さ \(H_i\) は、左側から来る制約と右側から来る制約の最大値です。

左側からの制約

左側、つまり \(j \leq i\) の区画から来る制約を

\[ L_i = \max_{j \leq i}(A_j - D(i-j)) \]

とします。

これは左から順に計算できます。

• \(L_1 = A_1\)
• \(i \geq 2\) のとき、

\[ L_i = \max(A_i, L_{i-1} - D) \]

です。

なぜなら、区画 \(i-1\) までの左側からの最大制約 \(L_{i-1}\) は、区画 \(i\) に進むと \(D\) だけ弱まるからです。

右側からの制約

同様に、右側、つまり \(j \geq i\) の区画から来る制約を

\[ R_i = \max_{j \geq i}(A_j - D(j-i)) \]

とします。

これは右から順に計算できます。

• \(R_N = A_N\)
• \(i \leq N-1\) のとき、

\[ R_i = \max(A_i, R_{i+1} - D) \]

です。

最終的な高さ

区画 \(i\) に必要な最終高さは、左からの制約と右からの制約の大きい方なので、

\[ H_i = \max(L_i, R_i) \]

です。

あとは、区画 \(i\) を \(A_i\) から \(H_i\) まで上げるためのコスト

\[ (H_i - A_i) \times C_i \]

をすべて足し合わせれば答えになります。

具体例

例えば、

\[ A = [10, 0, 0, 7], \quad D = 3 \]

とします。

左から見ると、

\[ L = [10, 7, 4, 7] \]

です。

高さ \(10\) の区画から右へ進むたびに、最低高さは \(7, 4\) と下がっていきます。

右から見ると、

\[ R = [10, 1, 4, 7] \]

です。

したがって最終的な高さは、

\[ H = [10, 7, 4, 7] \]

になります。

隣り合う差はすべて \(3\) 以下であり、これが必要最小限の高さです。

計算量

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

実装のポイント

左からの制約 \(L_i\) は配列に保存しておきます。

右からの制約 \(R_i\) は、右から走査しながら現在値 cur として持てばよいので、配列として保存する必要はありません。

各区画で

h = max(L[i], cur);

として最終的な高さを求め、

ans += 1LL * (h - A[i]) * C[i];

でコストを足します。

答えは最大で非常に大きくなるため、int ではなく long long を使う必要があります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, D;
    cin >> N >> D;

    vector<int> A(N), C(N), L(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> C[i];

    int cur = 0;
    for (int i = 0; i < N; i++) {
        if (i == 0) cur = A[i];
        else cur = max(A[i], cur - D);
        L[i] = cur;
    }

    long long ans = 0;
    for (int i = N - 1; i >= 0; i--) {
        if (i == N - 1) cur = A[i];
        else cur = max(A[i], cur - D);

        int h = max(L[i], cur);
        ans += 1LL * (h - A[i]) * C[i];
    }

    cout << ans << '\n';
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。