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)
二項係数の問題です。直感的に
数列 result1
を求めます(11ー15行目)。次に result1
の半分の値に近い値 result2
を求めます(17ー28行目)。問題で 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 の問題を紹介していきます。