JOI 一次予選 2024 (第 1 回) D - 現れている数字 (6Q, 難易度 2)

とても教育的な問題ですね。

• 問題へのリンク
• editorials

問題概要

0 以上 9 以下の整数からなる、 個の整数 が与えられる。

数列 の中に一度以上登場する整数を小さい順に出力せよ。

解法 (1)：値 0, 1, ..., 9 について個別に全探索

1 つめの解法は

• まず、値 0 が数列に含まれているかどうかを判定し、含まれていれば 0 を出力する
• 次に、値 1 が数列に含まれているかどうかを判定し、含まれていれば 1 を出力する
• 次に、値 2 が数列に含まれているかどうかを判定し、含まれていれば 2 を出力する
• ...
• 最後に、値 9 が数列に含まれているかどうかを判定し、含まれていれば 9 を出力する

という方法だ。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    for (int v = 0; v <= 9; ++v) {
        // A の中に v があるかどうかを調べる
        bool exist = false;
        
        for (int i = 0; i < N; ++i) {
            if (A[i] == v) {
                exist = true;
            }
        }
        
        if (exist) {
            cout << v << endl;
        }
    }
}

解法 (2)：バケット

解法 1 よりも高速な解法がある。それは次の配列 (しばしばバケットと呼ばれる) を用意することだ。公式解説もこの方法を解説している。

---

exist[v] ← 数列の中に値 の要素が存在するかどうかを表すブール値 (True / False)

---

最初は配列 exist 全体を False で初期化しておき、for 文を 1 回回して、各 i に対して

exist[A[i]] = true;

とすることで、配列 exist が求められる。

配列 exist が求められたら、あとは exist[0], exist[1], ..., exist[9] を順に調べて True である場合には対応する値を出力すればよい。

余談

なお、解法 (1) よりも解法 (2) の方が、計算量の観点では優れている。計算量については次の記事などで解説している。

qiita.com

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    // 値 v があるかどうか
    vector<bool> exist(10, false);
    for (int i = 0; i < N; ++i) exist[A[i]] = true;
    
    // 値 v を順に調べる
    for (int v = 0; v <= 9; ++v) {
        if (exist[v]) {
            cout << v << endl;
        }
    }
}