けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 057 D - Maximum Average Sets (400 点)

これは単に二項係数知っているかを問う感じ...?
この頃と今とでは、多少問題傾向も違う気がする。

問題へのリンク

問題概要

 N 個の数値が与えられる。このうち  A 個以上  B 個以下を選ぶときのその平均値の最大値を求めよ。
また最大を達成する選び方が何通りあるかを求めよ。

制約

  •  1 \le A \le B \le N \le 50

考えたこと

まずは最大となる場合としてどんなものがあるかを考えよう。普通は大きい順に選ぶとよさそう。

大きい順に何個選ぶかであるが、初期の数値によって変わってくる。例えば、 A = 9 であって大きい順に 9 個選んで

9, 9, 9, 9, 8, 8, 7, 7, 7

と選んだとすると、この平均値は 7 よりも大きな値となっていて、今後出てくる数は 7 よりも小さいことが保証されるので、ここで止めるべきである。一方

7, 7, 7, 7, 7, 7, 7, 7, 7

と選んでいた場合は平均値は 7 であり、今後 7 が登場する限りは選び続けても変わらない。よって


  • 大きい順に  A 個選んだとき、それらの値がすべて同じであるとき、その値の個数を  V として、 V 個から  A 個以上  B 個以下選ぶ場合の数を求めればよい。

  • そうでないとき、 A 個の値のうち最小の値を  v として、全体の中から  v の値をもつ数値が  V 個、 A 個の中から  v の値をもつものが  a 個あったとすると、 V 個から  a 個選ぶ場合の数を求めればよい。


なお、二項係数の求め方としては今回は普通に漸化式による方法が使える。

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

long long com[51][51];
int main() {
    com[0][0] = 1;
    for (int i = 1; i < 51; ++i) {
        for (int j = 0; j <= i; ++j) {
            com[i][j] += com[i-1][j];
            if (j > 0) com[i][j] += com[i-1][j-1];        
        }
    }

    int N, A, B; cin >> N >> A >> B;
    vector<long long> v(N);
    for (int i = 0; i < N; ++i) cin >> v[i];
    sort(v.begin(), v.end(), greater<long long>());

    // 最大値
    long long sum = 0;
    for (int i = 0; i < A; ++i) sum += v[i];
    double ave = (double)(sum) / A;

    // 小さいやつの個数
    long long res = 0;
    int num = 0;
    for (int i = 0; i < N; ++i) if (v[i] == v[A-1]) ++num;
    if (v[0] == v[A-1]) {
        for (int j = A; j <= B; ++j) {
            res += com[num][j];
        }
    }
    else {
        int a = 0;
        for (int i = 0; i < A; ++i) if (v[i] == v[A-1]) ++a;
        res = com[num][a];
    }
    cout << fixed << setprecision(10) << ave << endl;
    cout << res << endl;
}