解法1: バケットソートの要領で実装する

バケットソート の要領でこの問題の実装をすることができます。

\(bucket[x]=0\) で初期化された配列を用意した上で、 \(A\) に値 \(x\) が出現したときに \(bucket[x]=1\) と変更します。
その後、 \(i=1,2,\dots,N\) について \(bucket[i]=0\) なら挙げるべき整数として \(i\) を追加します。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> bk(n+1,0);
  for(int i=0;i<m;i++){
    int a;
    cin >> a;
    bk[a]=1;
  }
  vector<int> res;
  for(int i=1;i<=n;i++){
    if(bk[i]==0){
      res.push_back(i);
    }
  }
  cout << res.size() << "\n";
  for(int i=0;i<res.size();i++){
    if(i){cout << " ";}
    cout << res[i];
  }cout << "\n";
  return 0;
}

解法2: \(A\) をソートして調べる

\(A\) を昇順ソートした上で、次の通りにすることでこの問題に正解できます。

• \(p = 1\) とする。
• \(i = 1,2,\dots,N\) について、次を繰り返す。
  • \(p \le M\) かつ \(A_p = i\) である時、 \(p\) に \(1\) 加算する。
  • そうでない時、挙げるべき整数に \(i\) を追加する。

例えば、 \(N=6, M=3, A=(1,2,5)\) であるとき、次のように動作します。

• \(p=1\) とする。
• \(i=1\) について、 \(A_p = A_1 = 1\) なので、 \(p\) を \(2\) とする。
• \(i=2\) について、 \(A_p = A_2 = 2\) なので、 \(p\) を \(3\) とする。
• \(i=3\) について、 \(A_p = A_3 = 5 \neq 3\) なので、 \(3\) を挙げる。
• \(i=4\) について、 \(A_p = A_3 = 5 \neq 4\) なので、 \(4\) を挙げる。
• \(i=5\) について、 \(A_p = A_3 = 5\) なので、 \(p\) を \(4\) とする。
• \(i=6\) について、 \(p = 4 > M = 3\) なので、 \(6\) を挙げる。

この解法は \(A\) が相異なることで成り立っています。もし \(A\) 中に重複がある場合に対応するには、この解法を修正する必要があります。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(m);
  for(auto &nx : a){cin >> nx;}
  sort(a.begin(),a.end());
  int p=0;
  vector<int> res;
  for(int i=1;i<=n;i++){
    if(p>m){res.push_back(i);}
    else if(a[p]!=i){res.push_back(i);}
    else{p++;}
  }
  cout << res.size() << "\n";
  for(int i=0;i<res.size();i++){
    if(i){cout << " ";}
    cout << res[i];
  }cout << "\n";
  return 0;
}