AtCoder ABC 073 C - Write and Erase (4Q, 灰色, 300 点)

色々な解法があるが、set を使うのが楽。set のよい練習問題とも言える。

• 問題へのリンク

問題概要

最初何も書いていない黒板がある。次の 回の操作を行った。

• 回目の操作では、整数 を考える
• 黒板に が書かれていない場合は、新たに を黒板に書く
• 黒板に が書かれている場合は、それを消す

すべての操作を終えたあとの、黒板に書かれている整数の個数を答えよ。

制約

• 
• 

考えたこと

ここでは、「黒板に書かれた整数」を管理するための集合型変数 S を定義することにしょう。

次のコードのようにして、「書かれていたら削除」「書かれていなかったら挿入」を実現できる。

なお、これらの操作に要する計算量は である。全体として、 の計算量となる。

コード

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

int main() {
    int N, A;
    cin >> N;
    set<int> S;
    for (int i = 0; i < N; i++) {
        cin >> A;

        // A が S に含まれるならば、S から削除する
        if (S.count(A)) S.erase(A);

        // A が S に含まれていないないならば、S に挿入する
        else S.insert(A);
    }
    cout << S.size() << endl;
}