問題概要

長さ $N$ の数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。

$A$ に出現する整数のうち、出現回数が最小である整数を出力せよ。そのようなものが複数あるときは、そのうちの最小の整数を出力せよ。

制約

$1 \le N \le 100$
$1 \le A_{i} \le 2000$

解法

このような出現頻度に関する問題では、バケットや連想配列を使うとよいでしょう。今回は次のような配列を作ります。

con[v] ← 数列 $A_{1}, A_{2}, \dots, A_{N}$ の中に、整数値 $v$ が何個あるか

問題なのは、この配列 con のサイズをどのようにするべきか、というところでしょう。ここで制約を見ます。 $A_{i} \le 2000$ とあるので、配列 con のサイズを 2000 以上の適当な値にすればよいでしょう。

このような配列 con さえ求められれば、

con[v] > 0 であるような整数値 $v$ について、
con[v] が最小であるものについて、
v の値の最小であるものを求める

というようにすればよいでしょう。

コード

#include <bits/stdc++.h>
using namespace std;
const int MAX = 2100;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), con(MAX + 1, 0);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        ++con[A[i]];
    }
    
    int min = N + 1, min_v = -1;
    for (int v = 0; v < MAX; ++v) {
        if (con[v] == 0) continue;
        if (min > con[v]) {
            min = con[v];
            min_v = v;
        }
    }
    cout << min_v << endl;
}

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

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

JOI 一次予選 2022 (第 2 回) D - 希少な数 (6Q, 難易度 2)

問題概要

制約

解法

コード