バケットを用いた集計処理や、Greedy の練習！

問題へのリンク

問題概要

$N$ 個の整数 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。いくつかの整数を他の好きな整数に書き換えることで、数列に含まれる整数値の種類数が $K$ 以下となるようにしたい。

書き換える整数の個数の最小値を求めよ。

制約

$1 \le K \le N \le 2 \times 10^{5}$
$1 \le A_{i} \le N$

考えたこと

このような「各整数が何個ずつあるんだろうか」を考えたい問題では、次のような配列を用意しよう！

num[v]：データの中に、値が $v$ の要素が何個あるか

今回は、値として考えるべきものは $N$ 以下の整数なので、配列サイズも小さくて済む。他の問題を解くときに、もし、値が $10^{9}$ のような大きなものになりうる場合には、map 型などの連想配列を用いるとよい。

たとえば、 $A = (3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9, 9, 3, 2, 3)$ 、 $K = 3$ の場合を考えてみよう。まず $A$ を num で表すと、次のようになる。

1：2 個
2：2 個
3：4 個
4：1 個
5：2 個
6：1 個
7：0 個
8：0 個
9：3 個

種類数を $3 (= K)$ 以下にするためには、個数が大きい順に $K$ 個を残して、それ以外を「個数最大の要素」などに書き換えてあげればよい。上の例でいえば、個数が小さい順に並べると (0 個は無視している)、

4：1 個
6 ：1 個
1：2 個
2：2 個
5：2 個
9：3 個
3：4 個

となる。個数の多い 5, 9, 3 を残して、それ以外の 4, 6, 1, 2 をすべて 3 に書き換えればよい。この場合の答えは、

1 + 1 + 2 + 2 = 6

となる。同様に、一般のデータに対しても、個数の多い順に $K$ 種類を残して、それ以外を書き換えればよい。

計算量は $O(N \log N)$ となる (個数順にソートする部分がボトルネック)。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N), num(N+1, 0);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        num[A[i]]++;
    }

    vector<int> vec;
    for (int v = 0; v < num.size(); v++) {
        if (num[v] > 0) vec.emplace_back(num[v]);
    }
    sort(vec.begin(), vec.end());

    int res = 0;
    for (int i = 0; i < (int)vec.size() - K; i++) res += vec[i];
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 081 C - Not so Diverse (5Q, 茶色, 300 点)

問題概要

制約

考えたこと

コード