Various Sushi

おいしさ d の大きい順から寿司を K 個取ってみる

選んだ寿司のネタが x 種類だとすると、最適解はネタの種類数が x, x+1, ..., N のいずれかになる

しかも (解は持ってる寿司と残ってる寿司をひとつずつ交換して得られるのだけど)

ネタの種類数が 1 大きくなるような交換のみ考えればよい

たとえば K = 5 で今持っているネタが p, p, q, q, r のとき、交換後に

p, q, q, r, s (p が出て s が入った)

p, p, q, r, s (q が出て s が入った)

となるケースは答えが改善しうる

一方で

p, p, q, q, s (r が出て s が入った)

p, q, q, q, r (p が出て q が入った)

のような場合、答えがよくなることはない

これは、出る寿司のおいしさ > 入ってくる寿司のおいしさ から分かる (たぶん)

「種類 t の寿司をいくつ持っているか」「手元の寿司で美味しさが最大のもの」あたりを管理して

寿司を交換したときの損得を計算していくことで解ける