ABC116-D:Various Sushi - 思考の墓場

解法自体は素直なので400点なのだろうが，見た目はとっつきにくいので難しいと思った。

問題

考察・解法

食べることにする寿司の集合を $S$ ， $S$ のネタの種類を $f(S)$ と書くと， $\sum_{i\in S} d_i + f(S)^2$ の最大値を求めることになる。解法はさまざまだが，ここでは $d_i$ の和にまず注目することにする。この部分を最大化するのは簡単で， $d_i$ が大きい $K$ 個を取ればよい。これら $K$ 個の集合を $S_0$ としよう。これが最適解とは限らないというところが難しいのだが，これより良い解があるとしたら，それはネタの種類が $f(S_0)$ より大きい場合に限る。だから， $f(S_0)$ からネタの種類が増えるように $S_0$ の要素の寿司を交換していくことを考えたくなる。さらにこのとき，おいしさの和の項ができるだけ大きくなるようにする(どうしても小さくなるわけだが，それを最小限にする)必要がある。これはどのようにすれば効率的な計算時間で可能だろうか？

まず， $S_0$ を決めるために $(d_i,t_i)$ でソートしておく。これにより $d_i$ が大きい方から $K$ 個とり， $S_0$ と $f(S_0)$ を計算する。さらに，実際に $S_0$ に含まれるネタの種類とそれぞれの種類の寿司の数を記録しておく。ここまでやってスタートである。
ここからネタの種類を増やしていく。まず， $K+1$ 番目に $d_i$ が大きい寿司 $i$ のネタ $t_i$ の種類を見る。同じネタが $S_0$ にあるなら， $S_0$ のどの寿司を入れ替えてもネタの種類は増えないし，おいしさの和は減るだけなので，交換する必要はない。 $t_i$ が $S_0$ にない場合，何かと交換することでネタの種類が増える場合がある。この場合，交換に出すべき $S_0$ の寿司として最適なものは，「 $S_0$ に2つ以上含まれるネタの寿司の中で，もっともおいしさが小さいもの」である。このような寿司を選ぶことで，おいしさの和が小さくなることを最小限に抑えることができる。 $S_0$ に1つしか含まれない寿司を交換に出しても種類が変わらないことに注意しよう。
以上の手続きを繰り返すことで，おいしさの和を最小限に抑えながら，ネタの種類を増やしていくシミュレーションができる。食べる寿司の集合 $S$ が更新されるごとに答えの候補として試し，最大値を出力する。計算時間は $O(N)$ または $O(NlogN)$ でできる。

提出

Submission #4063050 - AtCoder Beginner Contest 116
これを実装してくださいと言われてもまだ大変かもしれない。上のコードでは， $S_0$ を求めたあと， $r=N-K+1$ とおき，これを交換する候補の最初のindexとしている。また，食べる寿司の集合のネタの種類と数はmapで管理した。ここから寿司 $r$ が交換に出す寿司の候補としてふさわしいか判断し，だめなら寿司 $r+1$ を試すということを繰り返している。 $r=N+1$ となったら，もう交換に出せる寿司の種類はないということなので，処理を終了してよい。mapを使っているので計算時間は $O(NlogN)$ となっている。

ABC Only回としては難しい，でもこういう問題好きです。
こどふぉと被っていて，こどふぉはratedなのでそっちに出ていた。
〇〇 Sushi という問題は難しめという謎の習慣...？