ARC100 (ABC102): C - Linear Approximation
問題
C: Linear Approximation - AtCoder Regular Contest 100 | AtCoder
解説
悲しさの式を読むと、 + (の添字) を加算している。の添字は予めから引いておくことで無視することができる。すると式は以下のように表せる。
の値を知りたい。最適なが分かっているとして、を動かしても悲しさの値が変わらないか、悪くなるような状態が考えられるようなは、の中央値と一致する。の量でイメージせず、最適値からの距離の変化(最適値から動かしたときの差分)をイメージすると良い。悲しさのグラフは中央値を頂点とするように下に凸になるため三分探索も思いつくが、離散的に解いた方がスマート。
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; }