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行)