AtCoder

ABC094 D問題(Binomial Coefficients)を解く

AtCoder_ABC094_D

AtCoder が提供しているABC(AtCoder Beginner Contest)094 D問題をC++で解いてみました。ABC094は、2018年4月14日21:00に実施されました。

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

D問題 Binomial Coefficients(Difficulty : 867)

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

ABC094 D問題 Binomial Coefficients

二項係数の性質を用います。AtCoder Problems による Difficulty は 867 でした。

解答案

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

二項係数の問題です。直感的に nCr の値は、n が大きく、rn の半分に近いときに最大となります。証明は公式解説をご覧ください。

数列 ai の最大値 result1 を求めます(11ー15行目)。次に result1 の半分の値に近い値 result2 を求めます(17ー28行目)。問題で ai>aj であることが条件となっているため、result2 の値は、result1 とは一致しないようにしています。

以下が、C++プログラムです。

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

#define INF (1 << 30)

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	int result1 = -1;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		result1 = max(result1, a[i]);
	}

	int result2 = result1;
	int t_min = INF;
	for (int i = 0; i < n; ++i) {
		if (a[i] == result1) {
			continue;
		}
		int t = abs(result1 / 2 - a[i]);
		if (t < t_min) {
			t_min = t;
			result2 = a[i];
		}
	}

	cout << result1 << " " << result2 << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

最後に

高校数学の復習でした。

引き続き ABC の問題を紹介していきます。

COMMENT

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

CAPTCHA