【AtCoder】ABC 392 B - Who is Missing? | 緑コーダーが解くAtCoder

atcoder.jp

配点: 200 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 29

問題概要
制約
考察
実装例
コメント

問題概要

長さ $M$ の整数列 $A$ が与えられる。 $A$ の各要素は $1$ 以上 $N$ 以下で、互いに相異なるという。

$A$ の要素として含まれない $1$ 以上 $N$ 以下の整数を、昇順に全て列挙せよ。

制約

$1 \le M \le N \le 1000$
$1 \le A_i \le N$

考察

長さ $N$ のbool配列を用意し、falseで初期化しておく。

そして、この配列の $A_i$ 番目の要素をtrueと書き換える。

その後、先頭から走査してfalseであるインデックスを、答えの配列に追加していけばよい。

実装例

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    rep(i, 0, M) cin >> A[i];

    vector<bool> num(N + 1);
    rep(i, 0, M) num[A[i]] = true;

    vector<int> ans;
    rep(i, 1, N + 1)
    {
        if (!num[i])
        {
            ans.push_back(i);
        }
    }

    cout << ans.size() << endl;
    for (auto x : ans)
    {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}