ABC094 D問題（Binomial Coefficients）を解く

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$ が大きく、$r$ は $n$ の半分に近いときに最大となります。証明は公式解説をご覧ください。

数列 $a_i$ の最大値 result1 を求めます（11ー15行目）。次に result1 の半分の値に近い値 result2 を求めます（17ー28行目）。問題で $a_i>a_j$ であることが条件となっているため、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 の問題を紹介していきます。