Zenn
👋

ARC 100 | C - Linear Approximation

2020/11/16に公開
#
競プロ
#
式変換
tech

問題

https://atcoder.jp/contests/arc100/tasks/arc100_a

考えたこと

以下のように式を変形する。

abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))
= \sum_{i=1}^N abs(A_i - i -b)

A_i - iは定数なのでB_iと置き換えると以下となる

\sum_{i=1}^N abs(B_i - b)

B_iをソートしたとき、最小となるbはB_iの中央値である。(https://drken1215.hatenablog.com/entry/2019/06/15/114700 を参照。)

よってそのときのbを代入して答えを求めればいい。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i] -= (i + 1);
  }
  sort(a.begin(), a.end());
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ans += abs(a[i] - a[n / 2]);
  }
  cout << ans << endl;
}

参考

Discussion