abc057_d
考えたこと
和の比率の最大化に似た式変形ができるのではないか
平均値の最大化は和の比率の最大化で、分母がすべて1であるようなスペシャルケース
式変形してソートして大きい方から貪欲、二分探索、でOK
分母がすべて同じ値なので式変形で消えて、結局値を大きい方からソートしたものになる
最大になるような個数も求めよ、と言われている
大きい方から選んだ時に、最後に同率n個からk個を選ぶ形になる。ここでn個からk個を選ぶ組み合わせの数になる
公式解説
考察漏れ
選択する個数に幅がある
一般的には大きい方から選んだ場合、選択する個数を増やしても平均値が下がるだけ
例外が、平均値と増やす値が同じ場合、つまり最も大きい値の物がたくさんあって、そればかり選んでる場合
この時の数え上げはもう一手間必要
Related Pages
- →chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×arc110c×一回り小さい同じ形の問題×agc049b×abc103d×abc023d×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]