AtCoder

ABC043 C問題(いっしょ)を解く

AtCoder_ABC043_C

AtCoder が提供しているABC(AtCoder Beginner Contest)043 C問題をC++で解いてみました。ABC043は、2016年8月13日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 いっしょ(Difficulty : 712)

問題の詳細は、リンク先をご覧ください。

ABC043 C問題 いっしょ

書き換える整数を全探索します。AtCoder Problems による Difficulty は 712 でした。

解答案

C++ プログラム例(ABC043C)

整数がある範囲(100ai100)のすべての値について、実際に計算した最小値を求めました。

以下が、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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA