ARC100 (ABC102): C - Linear Approximation

問題

C: Linear Approximation - AtCoder Regular Contest 100 | AtCoder

解説

悲しさの式を読むと、b + (Aの添字) を加算している。Aの添字は予めA_iから引いておくことで無視することができる。すると式は以下のように表せる。

 \sum_{i=1}^{N} |A_i^{\prime} - b|

b の値を知りたい。最適なbが分かっているとして、bを動かしても悲しさの値が変わらないか、悪くなるような状態が考えられるようなbは、Aの中央値と一致する。A_iの量でイメージせず、最適値からの距離の変化(最適値から動かしたときの差分)をイメージすると良い。悲しさのグラフは中央値を頂点とするように下に凸になるため三分探索も思いつくが、離散的に解いた方がスマート。

int main() {
  int N; cin >> N;
  vector<int64_t> A; cin >> A;
  rep(i, N) {
    A[i] -= i;
  }
  sort(all(A));
  auto m = A[A.size()/2];
  int64_t sum = 0;
  rep(i, N) {
    sum += abs(A[i] - m);
  }
  cout << sum << endl;
}