ARC119 E: Pancakes

atcoder.jp

公式解説とは異なる方法で解きました。

解法

操作を一回もしないときの の値を求めておき、 とします。

または のときの見栄えの悪さの値は、 との差分を考えることで合計 で求めることができます。よって、 のときの見栄えの悪さの最小値を計算すればよいです。

以下、 に を加え半開区間で扱うことにすると、見栄えの悪さは となり、 は点 と点 のマンハッタン距離なので、以下の問題を解くことに帰着されます。

個の点 があり、点 の座標は である。また、点には重みがあり、点 の重み は である。 で 点 のマンハッタン距離を表すとき、 に対する の最小値を求めよ。

対称性より、 という条件は としてもよいです。点を 座標の昇順に番号を振り直し、 座標の昇順に点を処理するします。点 を見ていて点 を今まで処理した点とするとき、点 の番号が点 より小さければ見栄えの悪さは 、そうでなければ となります。よって区間の最小値を計算できるセグメント木を二本用意し、それぞれ と を点 の番号の位置に配置すると、各 についての処理を時間計算量 で行うことができ、全体の時間計算量は となります。

実装

atcoder.jp

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000000;
template <typename T>
struct segment_tree{
    int N;
    vector<T> ST;
    segment_tree(int n){
        N = 1;
        while (N < n){
            N *= 2;
        }
        ST = vector<T>(N * 2 - 1, INF);
    }
    void update(int k, T x){
        k += N - 1;
        ST[k] = x;
        while (k > 0){
            k = (k - 1) / 2;
            ST[k] = min(ST[k * 2 + 1], ST[k * 2 + 2]);
        }
    }
    T range_min(int L, int R, int i, int l, int r){
        if (R <= l || r <= L){
            return INF;
        } else if (L <= l && r <= R){
            return ST[i];
        } else {
            int m = (l + r) / 2;
            return min(range_min(L, R, i * 2 + 1, l, m), range_min(L, R, i * 2 + 2, m, r));
        }
    }
    T range_min(int L, int R){
        return range_min(L, R, 0, 0, N);
    }
};
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  long long S = 0;
  for (int i = 0; i < N - 1; i++){
    S += abs(A[i + 1] - A[i]);
  }
  long long ans = S;
  for (int i = 0; i < N - 1; i++){
    long long tmp = S - abs(A[i + 1] - A[i]) + abs(A[i + 1] - A[0]);
    ans = min(ans, tmp);
  }
  for (int i = 1; i < N; i++){
    long long tmp = S - abs(A[i] - A[i - 1]) + abs(A[N - 1] - A[i - 1]);
    ans = min(ans, tmp);
  }
  vector<long long> x(N - 1), y(N - 1), w(N - 1);
  for (int i = 0; i < N - 1; i++){
    x[i] = A[i];
    y[i] = A[i + 1];
    w[i] = abs(A[i + 1] - A[i]);
  }
  vector<pair<long long, int>> P(N - 1);
  for (int i = 0; i < N - 1; i++){
    P[i] = make_pair(x[i], i);
  }
  sort(P.begin(), P.end());
  vector<int> pos(N - 1);
  for (int i = 0; i < N - 1; i++){
    pos[i] = lower_bound(P.begin(), P.end(), make_pair(x[i], i)) - P.begin();
  }
  vector<pair<long long, int>> P2(N - 1);
  for (int i = 0; i < N - 1; i++){
    P2[i] = make_pair(y[i], i);
  }
  sort(P2.begin(), P2.end());
  vector<int> id(N - 1);
  for (int i = 0; i < N - 1; i++){
    id[i] = P2[i].second;
  }
  segment_tree<long long> ST1(N - 1), ST2(N - 1);
  for (int i : id){
    long long mn1 = ST1.range_min(0, pos[i]);
    ans = min(ans, S + mn1 + x[i] + y[i] - w[i]);
    long long mn2 = ST2.range_min(pos[i] + 1, N - 1);
    ans = min(ans, S + mn2 - x[i] + y[i] - w[i]);
    ST1.update(pos[i], -x[i] - y[i] - w[i]);
    ST2.update(pos[i], x[i] - y[i] - w[i]);
  }
  cout << ans << endl;
}