第11回日本情報オリンピック　予選３

2011年12月23日
情報オリンピック日本委員会

解説

最も単純な解法として，N 種類のトッピングのうちどれを載せてどれを載せないかを全て試して 1 ドルあたりのカロリーが最も高いものを選ぶという方法が考えられる． しかし，N 種類のトッピングから自由に載せるものを選ぶ方法は 2^N 通りあるので，N = 100 程度のデータでは時間がかかりすぎてしまう．

ここで，全てのトッピングは同じ値段なので，載せていないトッピング a であって『「載せているあるトッピング b 」よりカロリーが高い』ものがあれば，トッピング a をトッピング b の代わりに載せた方がカロリーの合計が大きくなり，したがって 1 ドルあたりのカロリーも多くなる．

よって，k 個のトッピングを載せたピザのうち 1 ドルあたりのカロリーが最も高いものは『カロリーが高い順に k 個のトッピングを載せたピザ』であることがわかる．

よって 0 ≦ k ≦ N なる各 k について『カロリーが高い順に k 個トッピングを載せたピザ』の 1 ドルあたりのカロリーを求め，それらのうち最大のものを出力すればよい． この方法なら (N+1) 種類のピザを調べればよいので高速に動作する．