ABC057 D - Maximum Average Sets - ツバサの備忘録

解法

平均値の計算方法を思い出すと、
$\frac{(データの値の総和)}{(データの個数)}$
ですので、データの個数はより少なく、そしてデータの値の総和はより大きいものを選んだ方が得になります。
ということで、一番少ない個数になるのは $A$ 個だけ選んだ時で、データの選び方は降順にソートしたデータを前から順番にとった場合になります。
ということで、まず平均値の最大値がすぐに求められます。
ということで、まずは $N$ 個のデータを降順にソートして、大きい方から $A$ 個だけ抽出し、平均の最大値を求めてしまいます。
さて、求めた値になるようなデータの選び方を探ります。
2パターンに場合分けをすることができます。
$A$ 個抽出したときのデータの最大値を $M$ 、最小値を $m$ とします。

$M=m$ のとき
選んだ $A$ 個の値はすべて同じ値になっています。
この値が $x$ 個存在するとき、 $A$ 個選ぶ方法は
$_x C _A$
となります。 $A+1$ 個以降も同様に
$_x C _{A+1}$
のようになっていくので、最終的に
$\sum_{i=A}^{min(x,B)}\ _x C _{i}$
が答えとなります。
$M \neq m$ のとき
このとき、 $A+1$ 個以上値を選んだ場合、必ず平均値が最大ではなくなってしまいます(まだ選んでいない数字は、必ず現在の平均値より小さい値になっているためです)。
よって、 $A$ 個しか値を選ぶことはできません。
が、 $m$ が $A+1$ 番目以降にも存在した場合、選ぶパターンを変更することができます。
$m$ の全体の個数を $x$ 、 $m$ が $A$ 個選んだ中に含まれる個数を $y$ とすると、答えは
$_x C _y$
となり、これが答えになります。
ということで、2つのパターンのどちらかに当てはめて計算すれば、答えを求めることができます。