考察

必要条件

条件を満たす数列 \(A'\) が満たす条件を考えます。

三角不等式より任意の \(i<j\) に対して

\(|A'_i-A'_j| \leq \sum_{k=i}^{j-1}|A'_k-A_{k+1}|\leq (j-i)D\)

が成り立ちます。 よって特に \(A'_i \geq A'_j -(j-i)D \geq A_j -(j-i)D\) が成り立ちます。

同様に任意の \(j<i\) に対して \(A'_i \geq A_j -(i-j)D\) が成り立ちます。

これらを合わせ、 \(A'_i\geq \max_{1 \leq j \leq N}(A_j-|i-j|D)\) が必要条件であることがわかります。

十分条件

逆に \(A'_i=\max_{1 \leq j \leq N}(A_j-|i-j|D)\) と定めた数列 \(A'\) が条件を満たすことを示します。

三角不等式 \(|i-j|\leq |i+1-j|+|i-(i+1)|\) より

\(\begin{aligned} A'_i&=\max_{1 \leq j \leq N}(A_j-|i-j|D)\\ &\geq\max_{1 \leq j \leq N}(A_j-(|i+1-j|+1)D)\\ &\geq\max_{1 \leq j \leq N}(A_j-|i+1-j|D)+D\\ &=A'_{i+1}+D \end{aligned}\)

であり、\(i\) と \(i+1\) を入れ替えて同様の議論をすることで \(A'_{i+1}\geq A'_i+D\) を得るので、 \(|A'_i-A'_{i+1}|\leq D\) が成り立ちます。

また、こうして作られた数列は明らかにコスト最小です。

実装

\(A'_i=\max_{1 \leq j \leq N}(A_j-|i-j|D)\) を愚直に計算すると \(\Theta(N^2)\) になり、実行時間制限に間に合わせることは非常に困難です。

ここで、新たな数列 \(P_i=A_i+Di\)、 \(M_i=A_i-Di\) を用いると、\( A'_i=\max(-Di+\max_{j<i}P_j, Di+\max_{j>i}M_i)\) となることから、 \(P,M\) の累積 max を予め求めておくことで、 \(A'_i\) は各 \(i\) に対して \(O(1)\) で求めることができます。

全体の計算量は \(O(N)\) です。

実装例 (C++)

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

int main(){
  int n;
  long long d;
  cin >> n >> d;

  vector<long long> a(n), c(n);
  for(int i=0; i<n; i++) cin >> a[i];
  for(int i=0; i<n; i++) cin >> c[i];

  vector<long long> p(n), m(n);
  for(int i=0; i<n; i++){
    p[i] = a[i] + d*i;
    m[i] = a[i] - d*i;
  }

  vector<long long> pmax(n);
  pmax[0] = p[0];
  for(int i=1; i<n; i++){
    pmax[i] = max(pmax[i-1], p[i]);
  }

  vector<long long> mmax(n);
  mmax[n-1] = m[n-1];
  for(int i=n-2; i>=0; i--){
    mmax[i] = max(mmax[i+1], m[i]);
  }

  vector<long long> aa(n);
  for(int i=0; i<n; i++){
    aa[i] = max(-d*i + pmax[i], d*i + mmax[i]);
  }

  long long ans = 0;
  for(int i=0; i<n; i++){
    ans += (aa[i]-a[i]) * c[i];
  }

  cout << ans << endl;
}

実装例 (Python)

N, D = map(int, input().split())
A = list(map(int, input().split()))
C = list(map(int, input().split()))

P = [A[i] + D*i for i in range(N)]
M = [A[i] - D*i for i in range(N)]

Pmax = [0] * N
Pmax[0] = P[0]
for i in range(1, N):
  Pmax[i] = max(Pmax[i-1], P[i])

Mmax = [0] * N
Mmax[-1] = M[-1]
for i in range(1, N):
  Mmax[~i] = max(Mmax[~i+1], M[~i])

AA = [max(-D*i + Pmax[i], D*i + Mmax[i]) for i in range(N)]

ans = sum((AA[i]-A[i]) * C[i] for i in range(N))
print(ans)