#include using namespace std; int main() { // 1. 入力情報取得. int N; cin >> N; double X[N]; for(int i = 0; i < N; i++) cin >> X[i]; // 2. 等差数列の情報を整理. // 2-1. A = Σxi, B = Σ(i - 1) * xi を 計算. double A = 0.0, B = 0.0; for(int i = 0; i < N; i++) A += X[i], B += (X[i] * i); // [入力例] // 3 // 3 3 4 // -> A=10 B=11 // cout << "A=" << A << " B=" << B << endl; // 2-2. 初項, 公差 を 計算. // 求めたい初項x, 公差d について, 以下の g(x, d), f(x, d) から, // ラグランジュの未定乗数法 を 用いて, x, d を 計算. // https://ja.wikipedia.org/wiki/ラグランジュの未定乗数法 // // g(x, d) = (-1) * A + N * x + N * (N - 1) * d / 2 // f(x, d) = (x1 - x) * (x1 - x) + (x2 - (x + 2 * d)) * (x2 - (x + 2 * d)) + ... // + (xN - (x + (N - 1) * d)) * (xN - (x + (N - 1) * d)) // F(x, d, λ) = f(x, d) - λ * g(x, d) // ∂F/∂x = ∂F/∂d = ∂F/∂λ = 0 を 計算すると, // ↓ // A = N * x + (N - 1) * N * d / 2 // B = (N - 1) * N * x / 2 + (N - 1) * N * (2 * N - 1) * d / 6 // を得る. // さらに, 上記の A, B の連立方程式を解くと, // x = 2 * ((2 * N - 1) * A - 3 * B) / (N * (N + 1)) // d = 6 * (2 * B - (N - 1) * A) / ((N - 1) * N * (N + 1)) // が得られる. double x = 2 * ((2 * N - 1) * A - 3 * B) / (N * (N + 1)); double d = 6 * (2 * B - (N - 1) * A) / ((N - 1) * N * (N + 1)); // [入力例] // 3 // 3 3 4 // -> x=2.833333333333333 d=0.500000000000000 // cout << fixed; // cout << "x=" << setprecision(15) << x << " d=" << setprecision(15) << d << endl; // 2-3. コスト を 計算. double cost = 0.0; for(int i = 0; i < N; i++) cost += (X[i] - (x + i * d)) * (X[i] - (x + i * d)); // [入力例] // 3 // 3 3 4 // -> cost=0.166666666666667 // cout << fixed; // cout << "cost=" << setprecision(15) << cost << endl; // 3. 出力. cout << fixed; cout << setprecision(15) << x << " " << d << endl; cout << setprecision(15) << cost << endl; return 0; }