結果

問題 No.731 等差数列がだいすき
コンテスト
ユーザー @abcde
提出日時 2019-04-14 20:38:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 1,500 ms
コード長 2,221 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,263 ms
コンパイル使用メモリ 160,672 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-19 11:39:59
合計ジャッジ時間 2,048 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
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;
    
}
0