Random Pair [CodeChef November Cook-Off 2017 A]

https://www.codechef.com/COOK88/problems/RNDPAIR

N個の配列Aがある。
この配列に対しi＜jである(i,j)の全ての組合せのA[i]+A[j]の最大を取る。
ここからランダムにi＜Jである(i,j)を取って、最大となる確率を求めよ。

解法

Nが小さいので全て数えてしまおう。
下の実装を見てみると分かりやすいかもしれない。

int N, A[101];
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    int ma = 0;
    rep(i, 0, N) rep(j, i + 1, N) ma = max(ma, A[i] + A[j]);
 
    double up = 0, dwn = 0;
    rep(i, 0, N) rep(j, i + 1, N) {
        if (A[i] + A[j] == ma) up++;
        dwn++;
    }
    double ans = up / dwn;
    printf("%.10f\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}