ABC461C - Variety

解法

基本的には貪欲に価値が高いものを選んでいけばよい。
ただし、色を最低でも $M$ 種類選ばなければいけない点に工夫が必要となる。

まず、手作業か何かでやるなら、以下のように考えることができる。
まず、各色の中で最も価値が高いものだけ見ていき、価値が高いものから $M$ 個を採用する。
その後、まだ採用していないものだけ見ていき、価値が高いものから $K-M$ 個を採用する。
しかし、プログラムで書くと若干面倒であるため、これを少し改良する。

後半で考える $K-M$ 回を、「一度採用した色との重複が許される上限回数」と読み替える。
すると、全ての宝石を価値の高い順に見て、以下の処理をすればよい。

• まだ採用したことがない色であれば、採用する。
• もう採用したことがある色であれば、重複上限が残っているか確認して、以下に分岐。

- 重複上限が残っていれば、採用して、重複上限を $1$ 減らす。
- 重複上限が残っていなければ、不採用。

採用した宝石が $K$ 個になった時点で打ち切って、採用した価値の合計を答えればよい。

入力例1での動作

入力を受け取る。
$C$ と $V$ は、価値 $V$ を前に出して、降順の priority_queue に入れておく。

n: 5
k: 3
m: 2
pq: {(50,1) | (30,1), (40,1), (10,2), (20,3)}

選んだことがある色の set を持っておく。
色の重複が何回まであっても許されるかを $3-2 = 1$ と求める。
採用した個数のカウンターも持っておく。

color_set: {}
allowed: 1
counter: 0

最も価値の高い宝石 (50,1) を取り出す。
新しい色なので、採用して color_set を更新。

pq: {(40,1) | (30,1), (10,2), (20,3)}
color_set: {1}
allowed: 1
counter: 1
result: 50

最も価値の高い宝石 (40,1) を取り出す。
既存色だが allowed が残っているので、採用して allowed を更新。

pq: {(30,1) | (10,2), (20,3)}
color_set: {1}
allowed: 0
counter: 2
result: 90

最も価値の高い宝石 (30,1) を取り出す。
既存色かつ allowed が残っていないので、不採用。

pq: {(20,3) | (10,2)}
color_set: {1}
allowed: 0
counter: 2
result: 90

最も価値の高い宝石 (20,3) を取り出す。
新しい色なので、採用して color_set を更新。

pq: {(10,2) | }
color_set: {1, 3}
allowed: 0
counter: 3
result: 110

注意点

宝石の価値をいくつも加算すると、int 型からはみ出る。
結果用変数には long long 型を用いること。

別解

特になし。