AtCoder が提供しているABC(AtCoder Beginner Contest)043 C問題をC++で解いてみました。ABC043は、2016年8月13日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 いっしょ(Difficulty : 712)
問題の詳細は、リンク先をご覧ください。
書き換える整数を全探索します。AtCoder Problems による Difficulty は 712 でした。
解答案
C++ プログラム例(ABC043C)
整数がある範囲(
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int result = 200 * 200 * 100;
for (int s = -100; s <= 100; ++s) {
int temp_min = 0;
for (int i = 0; i < n; ++i) {
temp_min += (s - a[i]) * (s - a[i]);
}
result = min(result, temp_min);
}
cout << result << endl;
return 0;
}
AC(Accepted=正しいプログラム)と判定されました。
最後に
この問題は、数学的に解けそうですが、計算が間に合う場合は全探索したほうが素早く解ける、というセオリーを学ぶため記事にしました。
引き続き ABC の問題を紹介していきます。