• 穴に歯が生えている状態を \(1\)
• 穴に歯が生えていない状態を \(0\)

として配列などを用いて管理します。

操作が行われた穴について、 \(0\) と \(1\) を反転することを繰り返したうえで、最後に値の総和を取ることでこの問題に正解できます。

tips: 変数 \(x\) に対して、 \(a\) と \(b\) とを ( if 文なしで) 反転 ( \(a\) だった変数を \(b\) に、 \(b\) だった変数を \(a\) に更新 ) させる簡潔な方法を紹介します。

• \(x = (a+b)-x\) と更新する。
• \(x = a \ \rm{xor} \ \)\(b\)\( \ \rm{xor} \ \)\(x\) と更新する。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,q;
  cin >> n >> q;
  vector<int> a(n,1);
  for(int i=0;i<q;i++){
    int t;
    cin >> t;
    a[t-1]^=1;
  }
  int s=0;
  for(auto &nx : a){s+=nx;}
  cout << s << "\n";
  return 0;
}