箱と鍵 (Boxes and Keys) [JOI 2021/2022 一次予選 (第1回) 過去問 D]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_d

解説

https://atcoder.jp/contests/joi2022yo1a/submissions/26486427

宝箱を中心に考えてみよう。
とある宝箱を開錠するためには書かれている番号と同じ番号が書かれた鍵が存在する必要がある。
よって、すべての宝箱についてループを書いて、その中で対応する鍵があるかどうかを確認しよう。
これも同様にすべての鍵についてループを書いて、存在するものがあるかどうかを探せばいい。

発展課題

今回は宝箱のループで100回のループ、鍵のループで100回のループを行ったので、全体で最大10000回のループを
行っていることになる。
鍵のループの部分はsetなどのデータ構造を使うことで、ループの回数を減らしてより高速に計算することが可能になる。
他にもソートを使ってうまくやる方法などもあるので、高速化の方法も考えてみるといいと思う。

より詳しく書くと今回の解法は計算量O(N²)であるが、O(NlogN)、O(N)まで改善ができる。
考えてみるといい。

int N, M, A[101], B[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];

    int ans = 0;
    for (int i = 0; i < N; i++) {
        bool ok = false;
        for (int j = 0; j < M; j++) {
            if (A[i] == B[j]) ok = true;
        }
        if (ok) ans++;
    }
    cout << ans << endl;
}