D - Maximum Average Sets https://atcoder.jp/contests/abc057/tasks/abc057_d 考えたこと 平均値の最大化 和の比率の最大化に似た式変形ができるのではないか 平均値の最大化は和の比率の最大化で、分母がすべて1であるようなスペシャルケース 式変形してソートして大きい方から貪欲、二分探索、でOK 分母がすべて同じ値なので式変形で消えて、結局値を大きい方からソートしたものになる 最大になるような個数も求めよ、と言われている 大きい方から選んだ時に、最後に同率n個からk個を選ぶ形になる。ここでn個からk個を選ぶ組み合わせの数になる 公式解説 考察漏れ 選択する個数に幅がある 一般的には大きい方から選んだ場合、選択する個数を増やしても平均値が下がるだけ 例外が、平均値と増やす値が同じ場合、つまり最も大きい値の物がたくさんあって、そればかり選んでる場合 この時の数え上げはもう一手間必要
