等差数列がだいすき [yukicoder No.731]

https://yukicoder.me/problems/no/731

前提知識

• 最小二乗法

解法

https://yukicoder.me/submissions/283487

N個の数を頂点(i, A[i])として考えると、求めたい答えはちょうど線形近似になっている。
そのため、線形近似式を最小二乗法で求めよう。
もう少し具体的にはこのサイトに載っている式からy=ax+bのa,bが求まる。
これで初項bと公差（傾き）aが得られたので、必要なコストはyとの差の二乗の総和となる。

int N, A[1010];
//---------------------------------------------------------------------------------------------------
pair<double, double> linearApproximation(vector<pair<int, int>> v) {
    int n = v.size();
    
    double xy = 0;
    rep(i, 0, n) xy += v[i].first * v[i].second;

    double x = 0;
    rep(i, 0, n) x += v[i].first;

    double y = 0;
    rep(i, 0, n) y += v[i].second;

    double xx = 0;
    rep(i, 0, n) xx += v[i].first * v[i].first;

    double a = (n * xy - x * y) / (n * xx - x * x);
    double b = (xx * y - xy * x) / (n * xx - x * x);
    return { a,b };
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    vector<pair<int, int>> v;
    rep(i, 0, N) v.push_back({ i, A[i] });

    double a, b;
    tie(a, b) = linearApproximation(v);

    printf("%.10f %.10f\n", b, a);
    double c = 0;
    rep(i, 0, N) {
        double y = a * i + b;
        double d = y - A[i];
        c += d * d;
    }
    printf("%.10f\n", c);
}