ABC102（中央値舐めてたらやっつけられた件）

Atcoder ABC102

7月1日のABC102に出場したので書く。
結果：C問解けなかったよおおおお
そういう訳です。嘆いていてもアレなので書きます。

問題を解いていた最中

まず、b = 0として、次の式を考えた。理由としては、bを無視してみたらどうなるか見てみたかったから。

f_0=\sum 
\bigl|
A_i - i
\bigr|

次に、サンプルを入れて絶対値の中身を項ごとに見ていき、平均とったらいいのかなとか思っていた。
しかし、平均を取ってみてもうまくいかず、色々と迷走した後時間切れとなってしまった。結局中央値という単語すら思い浮かばなかった。

中央値とは

競技が終わって解説を読んだ僕は、なぜ中央値なのか納得が行かなかったので調べてみた。

\sum
\bigl|
X_i - t
\bigr|

突然だが中央値の定義は、上式を最小化するtの事である。また、Xは分布である。
日本語にすると「ある代表値ｔと分布に含まれる各値との距離の和が最小となるときの代表値ｔが中央値」である。

そんな定義だったんだ...数えて真ん中の奴!!!ぐらいの認識でしかなかった...
（完全に中央値舐めてる、タイトル回収）

中央値の定義を踏まえて問題を解く

さて、中央値についてもちょっとだけ詳しくなったので問題にチャレンジしてみる。
問題の式をfとおく、以下、式変形。

f=\sum
\bigl|
A_i - b - i
\bigr|

=\sum
\bigl|
(A_i - i) - b
\bigr|

ここで、A_i - i = X_iと置くと、

f = \sum
\bigl|
X_i - b
\bigr|

なんか変形していくと上で見た中央値の定義式が出てきましたね。
さて、問題の目的はfを最小化することでした。fを最小化した場合bは中央値になることは定義から明白です。
あとはコードに起こすだけですね、頑張りましょう。

書いたコード

#include<bits/stdc++.h>
using namespace std;
const int limit = 200050;

int main(){
    int n;
    cin >> n;

    int a[limit];
    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i] = a[i] - i - 1;
    }

    sort(a, a + n);

    int b = (n % 2 == 0) ? a[n / 2 - 1] : a[(n + 1) / 2 - 1];

    long long f = 0;
    for(int i = 0; i < n; i++) f += abs(a[i] - b);

    cout << f << endl;

    return 0;
}

無事、上記のコードでAC出来ました。
次はもっと頑張りたいですね。