概要

本問題は、隣接する区画の路面の高さの差がすべて \(D\) 以下になるように、各区画の路面を最小コストでかさ上げする問題です。 各区画を「条件を満たすために最低限必要な高さ」まで引き上げることが最適であり、これは左右からの累積的な制約を考慮することで、線形時間 \(O(N)\) で解くことができます。

考察

1. 問題の言い換え

各区画 \(i\) の最終的な高さを \(A'_i\) とします。満たすべき条件は以下の通りです。 - 任意の \(i\) について、 \(A'_i \geq A_i\)（路面を低くすることはできない） - 任意の \(i\) について、 \(|A'_i - A'_{i+1}| \leq D\)

また、各区画を \(1\) 高くするコスト \(C_i\) はすべて正（\(C_i \geq 1\)）であるため、コストを最小化するためには各 \(A'_i\) を条件を満たす範囲で極限まで小さくする必要があります。

2. 隣接条件が意味すること

条件 \(|A'_i - A'_{i+1}| \leq D\) は、変形すると以下のようになります。 - \(A'_i \geq A'_{i+1} - D\) - \(A'_{i+1} \geq A'_i - D\)

これをさらに広げて考えると、任意の区画 \(i\) と \(j\) について、 $\(A'_i \geq A'_j - |i - j| \times D\)\( が成り立つ必要があります。すなわち、ある区画 \)j\( の高さが \)A’_j\( であるとき、そこから \)1\( マス離れるごとに、高さの下限は \)D\( ずつ下がっていきます。 したがって、区画 \)i\( の最終的な高さ \)A’_i\( は、**すべての区画 \)j\( から受ける高さの下限の制約の最大値**、すなわち \)\(A'_i = \max_{1 \leq j \leq N} (A_j - |i - j| \times D)\)$ 以上でなければなりません。コストを最小化するためには、この下限ぴったりに高さを合わせるのが最適です。

3. 高速化のアプローチ（素朴な計算からの脱却）

すべての \(i, j\) の組み合わせについて上記の最大値を求めようとすると、 \(O(N^2)\) の計算量がかかってしまい、 \(N \leq 10^6\) では実行時間制限（TLE）に間に合いません。

そこで、自分より「左側にある区画」からの制約と、「右側にある区画」からの制約を分けて考えます。

• 左からの制約 \(L[i]\): 区画 \(i\) の左側（\(1\) から \(i\) まで）の初期高さのみを考慮したときの、区画 \(i\) に必要な最小の高さ。
• 右からの制約 \(R[i]\): 区画 \(i\) の右側（\(i\) から \(N\) まで）の初期高さのみを考慮したときの、区画 \(i\) に必要な最小の高さ。

これらは、動的計画法（DP）のように手前の結果を利用することで、それぞれ左から右、右から左への \(1\) 回の走査（\(O(N)\)）で計算できます。

具体例

\(N = 3, D = 10\), 初期高さ \(A = [10, 50, 20]\) とします。

1. 左からの伝搬 \(L\)

   • \(L[0] = A[0] = 10\)
   • \(L[1] = \max(A[1], L[0] - D) = \max(50, 10 - 10) = 50\)
   • \(L[2] = \max(A[2], L[1] - D) = \max(20, 50 - 10) = 40\)
   • \(L = [10, 50, 40]\)

2. 右からの伝搬 \(R\)

   • \(R[2] = A[2] = 20\)
   • \(R[1] = \max(A[1], R[2] - D) = \max(50, 20 - 10) = 50\)
   • \(R[0] = \max(A[0], R[1] - D) = \max(10, 50 - 10) = 40\)
   • \(R = [40, 50, 20]\)

最終的な目標の高さ \(target\_height[i]\) は、左右からの制約の厳しい方（大きい方）を採用すればよいため、\(\max(L[i], R[i])\) となります。 - \(target\_height = [\max(10, 40), \max(50, 50), \max(40, 20)] = [40, 50, 40]\)

この高さであれば、隣接差はすべて \(10\) 以下（\(D\) 以下）となり、条件を満たします。

アルゴリズム

1. 配列 \(L\) の構築（左から右への走査）

   • \(L[0] = A[0]\) とします。
   • \(i = 1\) から \(N-1\) まで、 \(L[i] = \max(A[i], L[i-1] - D)\) によって順に求めます。

2. 配列 \(R\) の構築（右から左への走査）

   • \(R[N-1] = A[N-1]\) とします。
   • \(i = N-2\) から \(0\) まで逆順に、 \(R[i] = \max(A[i], R[i+1] - D)\) によって順に求めます。

3. 最小コストの計算

   • 各区画 \(i\) について、最終的な高さは \(target\_height = \max(L[i], R[i])\) となります。
   • かさ上げする高さは \(target\_height - A[i]\) であり、これにコスト \(C[i]\) を掛けたものの総和が答えとなります。

計算量

• 時間計算量: \(O(N)\) 左から右へのループ、右から左へのループ、および最終的なコスト計算のループの計 \(3\) 回の走査のみを行うため、全体として \(O(N)\) の時間計算量で処理が完了します。 \(N = 10^6\) でも高速に動作します。

• 空間計算量: \(O(N)\) サイズ \(N\) の配列 \(A, C, L, R\) を保持するため、空間計算量は \(O(N)\) となります。

実装のポイント

• オーバーフローの防止: コスト \(C_i\) や、かさ上げの高さ、および最終的な合計コストは非常に大きな値になる可能性があります。C++では int 型ではなく long long 型を使用して、計算途中のオーバーフローを防ぐ必要があります。

• 入出力の高速化: \(N = 10^6\) と入力の数が非常に多いため、C++では ios_base::sync_with_stdio(false); cin.tie(NULL); を用いて標準入出力を高速化することが推奨されます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;
    
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    vector<long long> C(N);
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
    }
    
    // Left-to-right propagation
    vector<long long> L(N);
    L[0] = A[0];
    for (int i = 1; i < N; ++i) {
        L[i] = max(A[i], L[i-1] - D);
    }
    
    // Right-to-left propagation
    vector<long long> R(N);
    R[N-1] = A[N-1];
    for (int i = N - 2; i >= 0; --i) {
        R[i] = max(A[i], R[i+1] - D);
    }
    
    // Calculate the minimum total cost
    long long total_cost = 0;
    for (int i = 0; i < N; ++i) {
        long long target_height = max(L[i], R[i]);
        total_cost += (target_height - A[i]) * C[i];
    }
    
    cout << total_cost << "\n";
    
    return 0;
}

---

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