第3回 ドワンゴからの挑戦状 予選-D：ネタだけ食べたい寿司
問題
つの寿司と
個の皿がある。シャリのみを食べる時、皿を消費する。シャリのみを食べるのは
回実施することができるが、
回実施したタイミングでその後は寿司を食べることができない。幸福度の最大値を求めよ。
考え方
個までの寿司を食べるとするとするとき、
から
個は効果が大きいシャリのみの寿司を食べて、
番目の寿司はシャリのみをたべるのが最適である。ここでいう効果が高いのは、シャリのみを食べたときとそうでないときの差が大きい寿司である。
範囲の 番目を保持するのは PriorityQueue で実現することができるので、予め
個はシャリのみの寿司を食べておき、
まで順に効果の小さいシャリのみの寿司を食べるのをやめて、
個目についてシャリのみを食べたときの最大値を求めれば良い。
なお、 のときは常に
個食べることができるのですべてシャリのみの寿司を食べるのが最適である。
Submission #3767336 - 第3回 ドワンゴからの挑戦状 予選
どこに着目して考察するべきだったか
つの寿司はシャリだけ食べてしまったことにすると考えやすい。以降はシャリだけ食べる
個目の寿司について、今までシャリだけ食べたうち、価値の低い寿司はシャリも食べることにすると常に
個シャリだけ食べたことになる。
また、価値の低い寿司の考え方だが、これはシャリだけ食べたときとそうでないときの価値の差分で考えるとよい。
何がバグっていたか
得た知見
- 順序関係が定まる
つの要素を保持
- 差分で判断
