AtCoder ABC 350 B - Dentist Aoki (灰色, 200 点)

「集計処理」の基本問題！

• 問題へのリンク

問題概要 (意訳)

個の LED が最初はすべて光っている。

回の処理を行う。 回目の処理では 番目の LED の状態を flip する (光っていたら消して、消えていたら光らせる)。

最終的に何個の LED が光っているかを求めよ。

解法

次の配列を用意しよう。

---

• haeteru[v] ← 番目の LED が光っているとき 1、そうでないとき 0

---

このとき、 番目の LED を flip する操作は次のように書ける。

haeteru[v] = 1 - haeteru[v];

この実装によって、0 は 1 になり、1 は 0 になる。 回の処理を終えたあとは、 の個数を数えれば OK。

コード

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

int main() {
    int N, Q;
    cin >> N >> Q;
    
    vector<int> haeteru(N, 1);
    for (int i = 0; i < Q; ++i) {
        int T;
        cin >> T;
        --T;
        haeteru[T] = 1 - haeteru[T];
    }
    
    int res = 0;
    for (int i = 0; i < N; ++i) {
        res += haeteru[i];
    }
    cout << res << endl;
}