ABC102 C - Linear Approximation

C - Linear Approximation

問題概要

長さ N の整数列 A1,…,AN が与えられます。整数 b をいろいろ変えたときの

A1−(b+1)

+

A2−(b+1)

+⋯+

AN−(b+N)

の最小値を求めてください。

1≤N≤2×10の5乗

考えたこと

2次関数みたいなグラフになってると予想した。どっちかに動かせばどんどん小さくなるので、それを判定して出そうと思った。
途中で意味が分からなくなってあきらめた。

WAコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
int N;
 
int kaese(vector<int>A, int num) {
	int count = 0;
	int i = 0;
	while (1) {
		if (i == N) {
			break;
		}
		count += abs(A[i] - (num + i + 1));
		i++;
	}
	return count;
}
 
 
int main() {
 
	cin >> N;
	vector<int>A(N);
 
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
 
 
 
	//どっち向きに動かすか決める
	bool canr = false; bool canl = false;
	int base = kaese(A, 0);
	if (base == kaese(A, 1)) {
		cout << base;
	}
	if (base < kaese(A, 1)) {
		canl = true;
	}
	if (base < kaese(A, -1)) {
		canr = true;
	}
	if (canl && canr) {
		cout << base;
	}
 
	if (canl) {
		int i = -2;
		int back = kaese(A, -1);
		while (1) {
			int j = kaese(A, i);
			if (back < j) {
				cout << back;
				return 0;
			}
			back = kaese(A, i);
			i--;
		}
	}
	if (canr) {
		int i = 2;
		int back = kaese(A, 1);
		while (1) {
			int j = kaese(A, i);
			if (back < j) {
				cout << back;
				return 0;
			}
			back = kaese(A, i);
			i++;
		}
	}
}

参考

参考にさせて頂いたサイト
AtCoder ABC 102 C - Linear Approximation (ARC 100 C) (緑色, 300 点) - けんちょんの競プロ精進記録

まず、この [A-(b+1)]を変形して、分かりやすくすべき。
＝＞[x-Bi](Bi = Ai - i)
すると、|x−B1|+|x−B2|+⋯+|x−BN| となる

これはメディアンと呼ばれるもので、この形が出てきたら簡単に解けるらしい。

メディアンとは

中央値のこと。つまり、配列をsortし、その中央に出てきた値が、今回の答えだということ。

ACコード(けんちょんさん)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i], B[i] = A[i] - i;

    // メディアンを
    sort(B.begin(), B.end());
    long long x = B[N/2];

    // 答えを求める
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        res += max(x - B[i], -x + B[i]); // |A| = max(A, -A)
    }
    cout << res << endl;
}