ABC057 D Maximum Average Sets

D - Maximum Average Sets

ABC057 D Maximum Average Sets
問題概要
考察
- 提出コード

問題概要

N個の品物からA個以上B個以下選び平均の最大値とその選び方が何通りあるか答えなさい。

$1≦N≦50$

$1≦A≦B≦N$

$1≦v_i≦10^{50}$

$v_iは全て整数$

考察

k個目までの平均を $A(k)$ とします。 $v_{k+1}$ と $A(k)$ の大小関係によって $A(k+1)$ と $A(k)$ と大小関係が決まります。 $v_{k+1}≧A(k)$ であれば、 $A(k+1)≧A(k)$ のような具合です。

だから、問題の条件下における平均の最大値は $v_i$ の大きい方からA個選んだものということになります。また、平均がこの値を保ったままA個以上の数字を選べるのは、平均値がA番目に大きい $v_i$ と等しいときのみで、選べる数値はこの数のみです。この値を $v_A$ としたとき以下の2つの場合分けで答えを求めることが出来ます。