けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題概要 (意訳)

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

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

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

解法

次の配列を用意しよう。


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

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

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

この実装によって、0 は 1 になり、1 は 0 になる。 Q 回の処理を終えたあとは、 1 の個数を数えれば 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;
}