ABC116 D - Various Sushi
考え方は正しかったっぽいので、本番で解きたかった。 あとネタの種類に対して美味しさが複数値あり得るということにしばらく気付かなかった。サンプルとかちゃんと見よう。
解法
とりあえず美味しさが大きい順に取っていって、暫定の回答を作る。そこからちょっとずつ変えていって、比較して行けば良さそう。美味しさだけに注目して暫定解を作ったので種類を増やしていってボーナスを考慮した時に満足ポイントが上がるか試していく。種類を増やす為には暫定解から一つ寿司を削って選択していない中から選ぶが、この時に
- 種類を増やしていくので暫定解に含まれているネタ毎には最低一つは寿司を残す必要がある
- 暫定解に含まれるネタの寿司を後から選ばない
- 一つのネタの中で一番美味しい寿司を削っても意味ないので美味しさが小さいものから削っていく
- 同様に寿司を選ぶ時には新規ネタの中で一番美味しいものを選ぶ
よって、
- 暫定解
- 絶対に残す寿司
- 削ってもいい寿司
- 選んだネタの種類数
- 暫定解から削った寿司以外でまだ選ばれていない寿司
を管理すれば良さそう。さらに、まだ選ばれていないネタから寿司を選ぶ必要があり、その中でも美味しいものから選ぶ必要がある。 流れとしては
- 寿司を美味しい順に並べる
- 美味しいものからK個選んで暫定解を作るが、その際に選んだネタはあとで使わないようにマークしていく。また、ネタ毎に最初に出てきた寿司「以外」を保持する
- 選んでない(マークしていないネタの)寿司を美味しい順に見ていって、追加して満足ポイントが大きくなるか見ていく。その際には毎回計算するのではなく、差分を計算する方が早い
