概要

\(N\) 個の区画の高さを、隣り合う区画の高低差の絶対値が \(D\) 以下になるように調整する問題です。ただし高さは増やすことしかできず、区画 \(i\) を \(1\) 増やすコストは \(C_i\) です。合計コストの最小値を求めます。

考察

重要な観察1：各区画は「できるだけ低い」ほうが得

すべてのコスト \(C_i\) は正の値です。つまり、区画を高くすればするほどコストは増えます。したがって、条件さえ満たせるなら 各区画の高さはできる限り低いほうが得 です。

重要な観察2：各区画の「必要最小高さ」を独立に考えられる

条件 \(|A_i' - A_{i+1}'| \leq D\) は、次の \(2\) つに分解できます。

\[A_i' - A_{i+1}' \leq D \quad \text{かつ} \quad A_{i+1}' - A_i' \leq D\]

これを「区画 \(i\) の高さの下限」として見ると、次のようになります。

\[A_i' \geq A_{i+1}' - D, \qquad A_i' \geq A_{i-1}' - D\]

つまり 「隣が高いなら、自分もその高さから \(D\) を引いた値までは上げないといけない」 ということです。もともと \(A_i' \geq A_i\) でもあるので、まとめると各区画の高さは

\[A_i' \geq \max(A_i,\; A_{i-1}' - D,\; A_{i+1}' - D)\]

を満たす必要があります。

この下限をたどると

ある高い区画 \(j\) の高さ \(A_j\) は、\(1\) つ離れるごとに最大 \(D\) ずつしか下げられないため、区画 \(i\) の高さは必ず

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

を満たさなければなりません。これがすべての \(j\) について成り立つので、各区画の必要最小高さは

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

となります。これは、各区画から左右に傾き \(D\) の「山（三角形）」を広げたときの、その最も高い輪郭線に相当します。

この \(h_i\) は「すべての区画で同時に達成可能」であり、かつ「どの実行可能解でも必ず \(A_i' \geq h_i\)」なので、\(h_i\) を採用したときが最小コストになります。

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

「隣同士を \(1\) 回だけチェックして修正する」だけでは不十分です。ある高い区画の影響は左右へ次々と波及（カスケード）していくため、遠くの区画まで持ち上げる必要があるからです。すべての \(j\) について \(\max\) を直接計算すると \(O(N^2)\) となり、\(N \leq 10^6\) では間に合いません。

アルゴリズム

上記の \(h_i = \max_j(A_j - D|i-j|)\) は、左右 \(2\) 回のスキャンで \(O(N)\) で計算できます。

1. 初期化：\(h_i = A_i\)
2. 左から右へ：\(h_i \leftarrow \max(h_i,\; h_{i-1} - D)\) （左側にある区画の影響を右へ伝播）
3. 右から左へ：\(h_i \leftarrow \max(h_i,\; h_{i+1} - D)\) （右側にある区画の影響を左へ伝播）

累積的に最大値を持ち回るので、遠くの区画の影響も一度のスキャンで正しく伝わります。左向きの伝播をしたあとに、その値が再び右へ伝播し直す必要がないため、\(2\) 回のスキャンで十分です。

最後に、各区画で持ち上げた分のコストを合計します。

\[\text{コスト} = \sum_{i} C_i \cdot (h_i - A_i)\]

具体例

\(N=3,\ D=1,\ A=[0,0,5],\ C=[1,1,1]\) の場合：

• 左→右：\(h=[0,\,\max(0,-1)=0,\,\max(5,-1)=5]\)
• 右→左：\(h_1=\max(0,5-1)=4\)、\(h_0=\max(0,4-1)=3\) → \(h=[3,4,5]\)

高さ \(5\) の区画の影響で、左隣は \(4\)、さらにその左は \(3\) まで持ち上げる必要があります。コストは \(3+4+0=7\) です。

計算量

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

実装のポイント

• 最終的なコストは非常に大きくなり得ます。\(C_i\) は最大 \(10^7\)、持ち上げる高さや区画数も大きいため、コストの合計は int では必ずオーバーフローします。\(64\) ビット整数（long long）で計算してください。

• \(N \leq 10^6\) と入力が大きいため、高速な入力（自作の高速読み込みなど）を用いると安全です。

• \(2\) 回のスキャンでは、途中で更新した \(h\) の値を使って次の値を計算します（累積的に最大値を伝播させる点が重要です）。

  ソースコード

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

static char buf[1 << 25];
int bufpos, buflen;

inline int readInt() {
    int c;
    // skip non-digit
    while (true) {
        if (bufpos >= buflen) { buflen = (int)fread(buf, 1, sizeof(buf), stdin); bufpos = 0; if (buflen == 0) return -1; }
        c = buf[bufpos++];
        if (c >= '0' && c <= '9') break;
        if (c == '-') break;
    }
    bool neg = false;
    if (c == '-') { neg = true; }
    int x = (c >= '0' && c <= '9') ? c - '0' : 0;
    while (true) {
        if (bufpos >= buflen) { buflen = (int)fread(buf, 1, sizeof(buf), stdin); bufpos = 0; if (buflen == 0) break; }
        c = buf[bufpos++];
        if (c >= '0' && c <= '9') x = x * 10 + (c - '0');
        else break;
    }
    return neg ? -x : x;
}

int main() {
    int N = readInt();
    int D = readInt();
    vector<int> A(N), C(N), h(N);
    for (int i = 0; i < N; i++) A[i] = readInt();
    for (int i = 0; i < N; i++) C[i] = readInt();
    for (int i = 0; i < N; i++) h[i] = A[i];

    for (int i = 1; i < N; i++) {
        int cand = h[i-1] - D;
        if (cand > h[i]) h[i] = cand;
    }
    for (int i = N - 2; i >= 0; i--) {
        int cand = h[i+1] - D;
        if (cand > h[i]) h[i] = cand;
    }

    long long cost = 0;
    for (int i = 0; i < N; i++) {
        cost += (long long)C[i] * (long long)(h[i] - A[i]);
    }

    printf("%lld\n", cost);
    return 0;
}

---

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