ARC059C - いっしょ / Be Together

ずっとあなたと一緒（メンヘラ）

C - いっしょ / Be Together

提出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 でも問題なく収まるのでこの解法で行ける！！

・ 変更先はこれだ！ って絞る方法があるのかは知らない
全探索でいいんじゃないかな