AtCoder Beginner Contest 116：D - Various Sushi

問題

https://atcoder.jp/contests/abc116/tasks/abc116_d

考え方

x^2 の項をなんとかしたいので、まず食べる種類数 p 個を固定することを考えたい。

p 種類を選ぶときの最大値を考えよう。まず確実に p 種類のなかで、それぞれ一番おいしさの高い寿司は選ばれているはずである。残りは K-p 個の寿司を選ぶことになる。この時残りの寿司のうちおいしさの高い寿司から K-p 個選べばよい。

実は K-p 個選ぶ過程で p 種類以上の p' \ge p 個になったとしても問題ない。その場合は p' 個の一番おいしい寿司を選ぶ過程でより大きい値になるから、p 個選ぶ場合は最大値にはなりえないためである。

よって、寿司をそれぞれ種類ごとに、一番おいしさの高い寿司とそうでない寿司に分けて、それぞれ降順でソート済の配列の累積和を用いることで、種類数 p を全探索できるので O(N) で解を求めることができる。

Submission #4064605 - AtCoder Beginner Contest 116

別解

x 種類選んだときの「おいしさ基礎点」の最大値を f(x) として g(x) = f(x) + x^2 とすると凸関数であるから、三分探索で最大値を求めることができる。本当に凸関数であるかどうかは未証明である...。

Submission #4058251 - AtCoder Beginner Contest 116

どこに着目して考察するべきだったか

まずは x^2 の項を消したいので種類数を固定したい気持ちになる。あとは上から貪欲だが、損をする場合は最適値になりえないから無視してもよいという考え方が重要っぽい。

何がバグっていたか

得た知見(典型ポイント)

  • 大きいものから貪欲
  • ある変数を固定して全探索する
  • 最適な形/条件を考える

類題

  • C - All Green
    →最適でない場合は解になりえないから無視してよいのパターンに似ている気がする

参考