[AtCoder] ABC 156 C – Rally

2020年2月28日2020年12月15日

問題

方針

問題は最小二乗法に関するものなので、最適な座標は平均値となります。最小二乗法の解説が詳しいです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int X[N];
    ll sum = 0;
    for (int i = 0; i < N; i++) {
        cin >> X[i];
        sum += X[i];
    }
    ll ans1 = 0;
    ll ans2 = 0;
    for (int i = 0; i < N; i++) {
        ll t1 = (sum + N - 1) / N - X[i];
        ll t2 = sum / N - X[i];
        ans1 += t1 * t1;
        ans2 += t2 * t2;
    }
    cout << min(ans1, ans2) << "\n";
    return 0;
}