ずっとあなたと一緒(メンヘラ)
提出AC
Submission #8512086 - AtCoder Regular Contest 059
int main() { cout <<setprecision(10); ll n ; cin >> n ; vector<ll> a(n); rep(i,n) cin >>a[i]; ll ans = 100100100; for(int i = -100 ; i <= 100 ; i++){ ll tmp = 0; for(int j = 0 ; j < n ; j++){ tmp += (a[j] - i)*(a[j] - i); } chmin(ans,tmp); } cout << ans << endl; }
解法
全探索
要素数は最大100
変更する先の数値の候補(candidate)は-100 ~ 101 の201通り
100を-100にするときのコストは 40,000
candidate1つに対して、計算はそれぞれの要素に対してa[i] - candidate の2乗を求めるので
100回
それが最大200(ほぼ) なので20000回
そして、コストの最大値は要素数100個全部100 変更先が-100のとき
100 * 200^2 これは int でもlong long でも問題なく収まるのでこの解法で行ける!!
・ 変更先はこれだ! って絞る方法があるのかは知らない
全探索でいいんじゃないかな