水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

ABC057 : D - Maximum Average Sets

  • 問題

D - Maximum Average Sets

N 個のそれぞれ価値が決まった品物があり、そこから A 以上 B 以下個選ぶ。ここで、選んだ品物の価値の平均の最大値を求め、また、その最大値になるような品物の選び方の通り数を求める。

 

  • 解法

品物を価値でソートし、とりあえず A 個取る。その後、同じ要素を選べるならばできるだけ B 個へ個数を増やしていく。全部の個数ごとに選ぶ組み合わせ数を答えに加算していく。

 

  • 解答

Submission #2710157 - AtCoder Beginner Contest 057

f:id:babcs2035:20180621173954p:plain