はまやんはまやんはまやん

hamayanhamayan's blog

Binomial Coefficients [AtCoder Regular Contest 095 D]

https://beta.atcoder.jp/contests/arc095/tasks/arc095_b

解法

https://beta.atcoder.jp/contests/arc095/submissions/2361435

解法にたどり着いた過程を書く。
 
1. A[i]がmax 10^9なので、二項係数を真面目に計算しない
2. 計算する余地がない、かつ、まだ400点なので、考察が少し重めの問題ではないか
3. 最適解となるルールを探す
4. aiはなるべく大きい方が良さそう(仮定)
5. ajはai/2になるべく近いほうが大きくなる
6. aiを最大、ajをai/2になるべく近い数を採用して投げるとAC(自信が無くて実装前に解説をちら見した)

int N, A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);
 
    int ai = A[N - 1];
    int aj = A[0];
    rep(i, 0, N - 1) if (abs(A[i] - ai / 2) <= abs(aj - ai / 2)) aj = A[i];
    printf("%d %d\n", ai, aj);
}