けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 043 C - いっしょ (ARC 059 C) (茶色, 200 点)

本当にただ全探索するだけ!!!
でも意外とこういうのが思いつかれにくいかもしれない。

問題概要 (意訳)

長さ  N の整数列  a_{1}, \dots, a_{N} が与えられる。今、整数  x を 1 つ選ぶ。そして整数列をすべて  x に書き換える。それに要するコストは

  •  (x - a_{1})^{2} + \dots + (x - a_{N})^{2}

で与えられる。適切に  x を選んだときの、コストの最小値を求めよ。

制約

  •  1 \le N \le 100
  •  -100 \le a_{i} \le 100

考えたこと

 a_{1}, \dots, a_{N} の最小値を  m、最大値を  M としたとき、

  •  m より小さい  x は試す必要がない
  •  M より大きい  x は試す必要がない

ということがいえる。よってこの時点で、 x の候補は  m 以上  M 以下の整数値のみに限られた。これらをすべて調べて、その最小値を求めれば OK。計算量は  O(N(M-m)) となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    long long res = 1LL<<60;
    for (int x = -100; x <= 100; ++x) {
        long long tmp = 0;
        for (int i = 0; i < N; ++i) tmp += (x - a[i]) * (x - a[i]);
        res = min(res, tmp);
    }
    cout << res << endl;
}