Traveling Plan [AtCoder Regular Contest 093 C]

https://beta.atcoder.jp/contests/arc093/tasks/arc093_a

解法

https://beta.atcoder.jp/contests/arc093/submissions/2255525

i番目の観光スポットを訪れない時の金額の総和を効率よく求めるために差分だけ計算することで全体の計算を行わないあれをやろう。
まず「0->A[1]->...->A[N]->0」で必要な金額の総和を求めておこう（変数sm）
これを使うとi番目の観光スポットは以下のように計算できる。

• bをi番目の観光スポットの座標とする
• aをi-1番目の観光スポットの座標とする（存在しないなら0）
• cをi+1番目の観光スポットの座標とする（存在しないなら0）
• すると、i番目の観光スポットを訪れない時の金額の総和は「sm - (a->b) - (b->c) + (a->c)」となる

これを計算して、答える。

int N, A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    ll sm = 0;
    int x = 0;
    rep(i, 0, N) {
        sm += abs(x - A[i]);
        x = A[i];
    }
    sm += abs(x);
 
    rep(i, 0, N) {
        int a = 0;
        if (i) a = A[i - 1];
 
        int b = A[i];
 
        int c = 0;
        if (i != N - 1) c = A[i + 1];
 
        ll ans = sm;
        ans -= abs(a - b);
        ans -= abs(b - c);
        ans += abs(a - c);
 
        printf("%lld\n", ans);
    }
}