ABC094 D- Binomial Coefficients

#include <bits/stdc++.h>

using namespace std;
using ll =long long;

#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cout << #x << " = " << (x) << endl;

ll n,m;
string s;
//Write From this Line

int main()
{
    cout << setprecision(10);
    cin >> n ;

    vector<int> a(n);

    int M = 0;
    rep(i,n) {
        cin >> a[i];
        M = max(M,a[i]);
    }
    //天井 M / 2; に近いものを見つける

    ll search = (M+1) / 2 ;
    ll sa = M ;
    ll ans = M ;
    rep(i,n){
        ll tmp = abs ( search - a[i] );
        if(sa >= tmp){
            ans = a[i];
            sa = tmp;
        }
    }
    cout << M <<" " << ans << endl;

}

解法

Binomial Coefficientsは二項係数っていう意味。そもそもnCrが二項係数っていう考えが頭にしみついていなかったのでこの問題で染みつかせました。感覚的には、nが大きくて、rがnの半分に近いといいな。って思います。 nCr の意味は ( a + b) ^n を展開したときに出てくるa^n-rb^r係数の係数だった気がします。試しに 3C2 は ( a + b ) ^ 3 = a ^ 3 + 3(a²)b + 3a(b²) + b³ で、b²の係数からaをぶんどった3ですね。

で、これはパスカルの三角形でも求められて、三角形の中心にあるもののほうが係数が大きくなってるから、与えられた入力で一番大きいものをMをnにしてとしたとき、それの半分に近いものをrとして取ればよさそうだなってなります。

で、nが10なら5に近いもの、nが11なら 5 か6に近いものを探せばいいです。（11C5 = 11C6) で、これ一番大きい数Ｍが奇数のとき場合分けしないとダメかな。って思ったんですけど、変数searchを、(M +1) / 2 （つまり,M/2の小数点切り上げ)にして、それに近いものを与えられた入力から探したらACしちゃいました（嘘解法では？？？？？？？？？？？？？？？？？？？？）

嘘解法って言ってる理由は、11がＭだった時、小数点切り上げでsearch が 6 になるけど、このとき、6が入力になかったら 5か7を見つけるんですけど、5も7も入っていた時、たぶん5じゃなくて7を見つけちゃうことがあると思うんですよね。そういうこと

証明まがいなこと

公式の解説を見るのが一番いいんですけど,まあなんか、適当に書いていく。

nは大きい方がいい nCr のrを決め打ちしたとき（つまり、なんかの値に固定したとき) a < b の条件では aCr とbCr のどっちが大きいかって話になったとき、bCrのほうがどんな時でも大きいんですよね。というのも、b個からr個選ぶっていうのは,a個からr個選ぶよりも選択肢が増えている（b>a)なので。っていうので自明（本当か？）

rはn/2に近い方がいい こっちはまあ、[解法]のところで言ったパスカルの三角形考えればいいんじゃないかな？まあ、たぶん僕のは嘘解法なので、nが奇数のときは、nC(実際に得たsearch に近い数)を計算して、今まで出てきたnCrより更新する。みたいな感じでやればいいんじゃないでしょうか。おしまい