Atcoder Beginner Contest 057 D. Maximum Average Sets

Atcoder Beginner Contest 057 D. Maximum Average Sets

D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder

感想

なぜかWAのまま放置していた。

解法

なんかやるだけ。
ただし$\ {}_n C _r \ $を求めるためにはパスカルの三角形による計算をしなければいけないので一応メモっておく（今まで使ってことがなかったので、初めはBigintライブラリを貼り付けて適当に通した）。
$\ mod\ $をとる計算をしないので、$\ n \geq 67\ $のときlong long型ではオーバーフローするようだ。

実装

#include "bits/stdc++.h"
using namespace std;

#define all(x) x.begin(), x.end()

long long com[70][70]; //67以上でオーバーフロー
void init(int n) {
        for (int i = 0; i <= n; i ++) {
                for (int j = 0; j <= i; j ++) {
                        if (j == 0 || j == i) com[i][j] = 1LL;
                        else com[i][j] = com[i - 1][j - 1] + com[i - 1][j];
                } 
        }
}
long long nCr(int n, int r) { return com[n][r]; }

int main() {
        int n;
        init(66);
        cin >> n;
        long long a, b;
        cin >> a >> b;
        vector<long long> v(n);
        for (int i = 0; i < n; i ++) cin >> v[i];
        sort(all(v));
        reverse(all(v));
        long long sum = 0;
        long long mi;
        for (int i = 0; i < a; i ++) { 
                sum += v[i];
                if (i == a - 1) mi = v[i];
        }
        cout << setprecision(10) << (double)sum / (double)a << endl;
        bool can_add = true;
        for (int i = 0; i < a; i ++) if (v[i] != mi) can_add = false;
        int cnt_A = 0, cnt_B = 0, cnt_all = 0;
        for (int i = 0; i < a; i ++) if (v[i] == mi) cnt_A ++;
        for (int i = 0; i < b; i ++) if (v[i] == mi) cnt_B ++;
        for (int i = 0; i < n; i ++) if (v[i] == mi) cnt_all ++;
        long long ans = 0;
        for (int i = cnt_A; i <= (can_add ? cnt_B : cnt_A); i ++) ans += nCr(cnt_all, i);
        cout << ans << endl;
        return 0;
}