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

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

JOI 一次予選 2021 (第 1 回) C - 共通要素 (6Q, 難易度 2)

バケット 集計処理 連想配列(setやmap) 数列 そのまま覚えたい易しい教育的典型問題 AtCoder JOI JOI一次予選 JOI難易度2 NoviSteps6Q 全探索 全探索:整数値 易しい全探索

このような問題を解くためにも、「バケット」を習得しよう！

問題概要

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

こっらの数列の双方に登場する数をすべて昇順で出力せよ。

制約

  • 1 \le N, M \le 100
  • 1 \le A_{i}, B_{j} \le 100

解法 (1)：1 から 100 までの数を順に調べる

制約を見よう！！
そうすると、「 1 \le A_{i}, B_{j} \le 100 と書いてあるので、登場する数は 1 から 100 までしかありえないことがわかる。よって、次の解法が考えられる。

v = 1, 2, \dots, 100 について順に

  • v が数列 A に含まれるかを確かめる
  • v が数列 B に含まれるかを確かめる
  • ともに含まれるならば、その値を出力する

コード

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < M; ++i) cin >> B[i];
    
    for (int v = 1; v <= 100; ++v) {
        bool exist_in_A = false, exist_in_B = false;
        for (int i = 0; i < N; ++i) {
            if (A[i] == v) exist_in_A = true;
        }
        for (int i = 0; i < M; ++i) {
            if (B[i] == v) exist_in_B = true;
        }
        
        if (exist_in_A && exist_in_B) cout << v << endl;
    }
}

　

解法 (2)：バケットを使う

解法 (1) の「整数値 v が数列 A に含まれるか」(数列 B も) を判定する部分をより効率的にしよう。

そのためには、次のような配列を用意することが考えられる。なお、このような配列をバケットと呼ぶ。

  • exist_in_A[v] ← 整数値 v が数列 A に含まれるとき true、そうでないとき false
  • exist_in_B[v] ← 整数値 v が数列 B に含まれるとき true、そうでないとき false

この配列 exist_in_A、exist_in_B をあらかじめ作っておけば、整数値 v が数列 A, B に含まれるかどうかの判定を効率的に行える。

コード

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < M; ++i) cin >> B[i];
    
    vector<bool> exist_in_A(101), exist_in_B(101);
    for (int i = 0; i < N; ++i) exist_in_A[A[i]] = true;
    for (int i = 0; i < M; ++i) exist_in_B[B[i]] = true;
    
    for (int v = 1; v <= 100; ++v) {
        if (exist_in_A[v] && exist_in_B[v]) cout << v << endl;
    }
}