ARC095 D : Binomial Coefficients(400)

作成日:2018.09.09
最終更新日:2018.09.09

問題概要

問題本文

 $n$個の非負整数$a_1,a_2,...,a_n$から2つの異なる数$a_i , a_j$で$_{a_i}C_{a_j}$が最大となる組を答えよ。 但し、複数ある場合はいずれを答えても良い。
制約
$1 \leq n \leq 10^5$
$0 \leq a_i \leq 10^9$
$i \neq j$ならば$a_i \neq a_j$

考え方

 $_{a_i}C_{a_j}$$=\frac{a_i!}{a_j!(a_i-a_j)!}$$=\frac{a_i(a_i-1)...(a_i-a_j+1)}{a_j!}$である。 よって$a_j$を固定すると$a_i$は大きいほど良いということが分かる。 またパスカルの三角形を思い浮かべると、$a_i$を固定した時は$a_j$が$a_i/2$に近いほど良いことが分かる。 さらに$_xC_y = _xC_{x-y}$であるから、$a_j$としては$|a_j-a_i/2|$が一番小さくなるものを選べば良い。

ソースコード

マクロ等はこちら

int n,m;
int a[100010];

int main(){
	cin >> n;
	repp(i,0,n){
		cin >> a[i];
		m = max(m,a[i]);
	}
	int p = -1;
	repp(i,0,n) if(a[i] != m && abs(2*a[i]-m) < abs(2*p-m)) p = a[i];
	cout << m << ' ' << p << endl;
	return 0;
}

解法まとめ

 $a_i$としては最大のものを選び、$a_j$としては$a_i$でないもののうち$|a_j-a_i/2|$が最小となるものを選ぶ。(8,11行)

ARC095の他の問題 C E F

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告