けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 052 D - Walk and Teleport (2Q, 緑色, 500 点)

この時代は Greedy が多かった。そして、実はすごく単純なことに気がつくかどうかが問われる問題!

問題概要

数直線上 (東西方向) に  N 個の町があり、それぞれの町の座標は  X_{i} である。町 1 から出発して、すべての町を訪れたい。次の 2 つの手がある。

  • 東または西へ 1 移動する:コスト  A
  • ある町から他の町へとテレポートする:コスト  B

達成するための最小コストを求めよ。

制約

  •  2 \le N \le 10^{5}
  •  1 \le A, B, X_{i} \le 10^{9}
  •  X_{1} \lt X_{2} \lt \dots \lt X_{N}

考えたこと

一見すると、取り得る手がとても多くて、何から考えたらよいのかわからなく思えてしまう......こういうときは、「移動方法に制限を加えて解いても良い」という感じの考察が有効であることが多い。

さて、一般に 4 つの町 A, B, C, D について、下図の上側のような移動をするとする (途中テレポートを使ってもよい)。これは、下側のような移動に置き換えても、少なくともコストが悪化することはないことが言える (途中テレポートがあっても)。

このような考察を繰り返すことにより、結局

「町  1 2 3 → ... →  N

の順序で進んでいけばよいことがわかる。

残り

ここまで来ればもう簡単だ。町  i から町  i+1 へと移動するための最小コストは

min(A * (X[i+1] - X[i]), B)

と表せる。これを各  i について合算すればよい。計算量は  O(N) となる。

コード

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

int main() {
    long long N, A, B;
    cin >> N >> A >> B;
    vector<long long> X(N);
    for (int i = 0; i < N; ++i) cin >> X[i];
    
    long long res = 0;
    for (int i = 0; i + 1 < N; ++i) {
        long long diff = X[i + 1] - X[i];
        res += min(diff * A, B);
    }
    cout << res << endl;
}