[AtCoder] ABC116 D – Various Sushi

Various Sushi

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

考え方

題意

満足ポイントの最大値を出力します。

方針

種類数を固定したときの満足ポイントを計算し、種類数の最適値を求めます。

与えられた寿司の種類数を \( l_1 \) とします。ある種類の寿司のおいしさ基礎ポイントの最大値を持つ寿司のグループを \( G_1 \) とします。ただし、同じ種類の寿司が含まれることはありません。 したがって、\( G_1 \) の要素数は \( l_1 \) となります。\( G_1 \) に入らない寿司のグループを \( G_2 \) とします。\( G_2 \) の要素数 \( l_2 \) は、\( l_2 = N – l_1 \) となります。

また、\( G_1, G_2 \) はおいしさ基礎ポイントについて降順に整列されているとします。

  • \( l_1 = N\) のとき

このとき、\( K \) 種類の寿司を選ぶことになるので、\( G_1 \) の先頭から \( K \) 個寿司を選ぶことになります。

  • \( l_1 \neq N \) のとき

選ぶことのできる寿司の種類の最大値は、\( \min(K, l_1)\) となります。

ここで次の選び方を考えます。

  1. \( G_1 \) の先頭から \( i \) 個寿司を選ぶ。
  2. \( G_2 \) の先頭から \( K – i \) 個寿司を選ぶ。

このとき、選んだ寿司のおいしさ基礎ポイントの総和 \( T \) としたとき、満足ポイントを

\( T + i^2\)

と定義します。このように寿司を選んだ時、種類数が \( i \) よりも大きくなっている可能性がありますが、問題ありません。そのような \( i \) が最適ではないというだけなので、\( i \) を \( \min(K, l_1) \) から下限値まで探索することで最適値が求まります。

このような計算では、全ての可能な種類数の満足ポイントの最大値を求めることはできませんが、満足ポイントを最大化する種類数を求めることはできます。

また、おいしさ基礎ポイントの和を求めるために、各グループの累積和を計算しておくと、計算量が抑えられます。

コード

感想

こういう解き方があるのかと感心しました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする