https://atcoder.jp/contests/abc116/submissions/9809190
数学的要素は多くないが、dif16Kなのでデータ構造の扱いが難しい。
- 選択済み、未選択を高速に判別するためbool型配列とprioty queueに予めコンテナを分割するテクニック
- 美味しさが単調減少するため、ネタ要因で増加するかどうかチェックするだけで良くなる
なお、この問題は以下の2つのフェーズに分かれる。
- 美味しさを貪欲にK個選ぶ
- 交換することで更にスコアを向上させる
まず、フェーズ1について考える。ネタの種類数の加点を無視して美味しさの加点
だけで考えれば、大きい美味しさの🍣を貪欲にK個選べば良い。
しかし、本当の意味での最善では、美味しさを多少犠牲にしてでもネタの種類数を増やしたほうがで加点されるので良い可能性がある。よって、後々ネタの種類数を増やすために重複したネタか重複してないネタか高速に判別し、まだ選んでないN-K個のうちの🍣と交換する処理が必要になりそうと予想する。これはコンテナを2つ用意することで実現できる。具体的には大きい美味しさの🍣を貪欲にK個選ぶときに、1個目のネタ[i]ならbool型vector[i]にチェックを入れておき、2個目以降の重複ネタの🍣を昇順priority queueに格納する。このようにコンテナを予め2個に分けることで後々ネタが重複している🍣を高速に取り出すことが出来るようになる。
次に、フェーズ2について考える。美味しさについてはフェーズ1で最大化されているので、交換するほど減っていく。したがって、ネタの種類数の要因で美味しさの減少を上回るかどうかだけ意識すれば良い。
まだ選んでいないN-K個の🍣を順番に見ていき、ネタが重複している選択済み🍣と交換してスコアが高くなる場合に限り交換したい。スコアを最適に更新させるなら「選択済み🍣のうち美味しさが小さい物」と「未選択🍣のうち美味しさが大きい物」を交換するのが良さそうという気持ちになる。
選択済みと未選択の判別は前述のbool型vectorを参照すればで処理できる。交換するときはpriority queueをpopすれば
で実現する。選択済み🍣2個と未選択🍣2個を交換するのが最終的に最善としたとき、選択済み🍣1と未選択🍣2、選択済み🍣2と未選択🍣1、のようにペアを工夫して交換するべきか悩むかもしれない。しかし、ペアを工夫してもしなくても最終結果が同値になって2個交換するため、工夫せず順番に交換してくだけで最善が得られる。なお、交換して新たに選択済みになる🍣はpushする必要なくスコアに加算するだけで良い。
