概要

区画の路面の高さを高くすることしかできない状況下で、隣接する区画の高さの差を \(D\) 以下にするために必要な最小コストを求める問題です。

考察

各区画 \(i\) の高さを \(1\) 増やすコスト \(C_i\) はすべて正の値です。したがって、各区画の最終的な高さ \(A_i'\) を大きくすればするほど、コストは単調に増加します。

このことから、「すべての条件を満たす最終的な高さの中で、各区画の高さをできるだけ小さくしたもの」がコスト最小となることがわかります。言い換えると、\(A_i' \geq A_i\) かつ \(|A_i' - A_{i+1}'| \leq D\) を満たす整数の組 \((A_1', A_2', \ldots, A_N')\) のうち、各 \(A_i'\) が最小になるようなもの（点ごとの最小値）を求めればよいです。

この「点ごとの最小値」は、左から右へ、右から左への2回の走査によって効率的に求めることができます。

アルゴリズム

1. 左から右への走査: 左隣の区画からの制約を満たすように高さを決定します。

   • 最初の区画の高さは少なくとも \(A_1\) である必要があります。
   • \(i\) 番目の区画の高さは、\(A_i\) 以上であり、かつ左隣の高さ \(P_{i-1}\) から \(D\) を引いた値以上である必要があります（\(P_{i-1} \leq P_i + D \Leftrightarrow P_i \geq P_{i-1} - D\)）。
   • したがって、\(P_i = \max(A_i, P_{i-1} - D)\) として更新していきます。

2. 右から左への走査: 右隣の区画からの制約を満たすように高さを調整します。

   • 最後の区画の高さは少なくとも \(A_N\) である必要があります。
   • \(i\) 番目の区画の高さは、現在の \(P_i\) 以上であり、かつ右隣の高さ \(P_{i+1}\) から \(D\) を引いた値以上である必要があります（\(P_{i+1} \leq P_i + D \Leftrightarrow P_i \geq P_{i+1} - D\)）。
   • したがって、\(P_i = \max(P_i, P_{i+1} - D)\) として更新していきます。このとき、\(A_i\) も同時にチェックして下限を保ちます。

3. コストの計算: 最終的に求まった最小の高さ \(P_i\) に対して、合計コスト \(\sum_{i=1}^{N} C_i \times (P_i - A_i)\) を計算します。

計算量

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

実装のポイント

• 合計コストは \(N \leq 10^6\)、高さの増加量が最大 \(10^5 \times 10^6 = 10^{11}\)、\(C_i\) が最大 \(10^7\) となるため、\(10^{18}\) のオーダーになり得ます。そのため、合計コストを計算する変数には long long などの64ビット整数型を使用する必要があります。

• 左から右への走査と右から左への走査は、配列 P を一つ用意し、その場で更新することで簡潔に実装できます。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    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), C(N), P(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
    }
    
    // Left-to-right pass
    long long cur = A[0];
    for (int i = 0; i < N; ++i) {
        if (A[i] > cur) cur = A[i];
        P[i] = cur;
        cur -= D;
    }
    
    // Right-to-left pass
    cur = A[N - 1];
    long long ans = 0;
    for (int i = N - 1; i >= 0; --i) {
        if (A[i] > cur) cur = A[i];
        if (cur > P[i]) P[i] = cur;
        ans += C[i] * (P[i] - A[i]);
        cur -= D;
    }
    
    cout << ans << "\n";
    return 0;
}

この解説は or-glm5.2-high によって生成されました。