AtCoder Beginner Contest 102 解説備忘録

前書き

AtCoder Beginner Contest 102 を解いてみた．解けなかった問題の備忘録．

C問題

[問題はこちら]

・min $\sum |A_i-(b+i)|$を求める。

・$A_i-i=x_i$とし、$x_i$を昇順でソートする。

・ここで、$x_m-b \leq 0$、$x_{m+1}-b \leq 0$となる$m$を設定する。

・このとき、
$\begin{eqnarray}
\sum_{i=1}^{n} |x_i-b|&=& \{ \sum_{i=1}^{m} -(x_i-b) \} + \{\sum_{i=m+1}^{n} (x_i-b) \}
&=& \sum_{i=1}^{m}(-x_i) + \sum_{i=m+1}^{n}x_i + (2m-n)b
\end{eqnarray}
$
となる。
・$x_1 \leq x_2 \leq \cdots \leq x_m \leq x_{m+1} \leq \cdots \leq x_n$より、$m=n/2$すなわちソート後の中央値で最小となる。

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#include <stack>
#include <cstdlib>
#include <utility> //pair

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

typedef long long ll;

using namespace std;

int main() {

    ll n;
    cin >> n;

    vector<ll> a(n);

    FOR(i, 0, n){
        cin >> a[i];
        a[i] = a[i] -(i+1);
    }

    sort(a.begin(),a.end());

    ll b,b1,b2;
    ll ans=0;
    ll ans1=0,ans2=0;
    if(n%2!=0){
        b = a[n/2]; //中央値
        FOR(i, 0, n){
            ans += abs(a[i]-b);
        }
    }else{
        b1 = a[n/2];
        b2 = a[n/2-1];
        FOR(i, 0, n){
            ans1 += abs(a[i]-b1);
            ans2 += abs(a[i]-b2);
        }
        ans = min(ans1,ans2);
    }

    cout <<  ans <<  endl;

    return 0;
}

あとがき

精進します．