C++のSTLコンテナsetを用いてABC73 C問題を解く

競技プログラミングの備忘録用にメモ

今回はABC73 C問題をSTLコンテナのsetを用いて解く．

C - Write and Erase

問題文

あなたは、joisinoお姉ちゃんと以下のようなゲームをしています。

• 最初、何も書いていない紙がある。
• joisinoお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、書いていなければその数字を紙に書く。これを
  $ N $
  回繰り返す。
• その後、紙に書かれている数字がいくつあるかを答える。

joisinoお姉ちゃんが言った数字が、言った順番に$ A_1,...,A_N $として与えられるので、ゲーム終了後に紙に書かれている数字がいくつあるか答えてください。

制約

• $1≦N≦100000$
• $1≦A_i≦1000000000(=10^9)$
• 入力は全て整数である。

全探索ではもちろん間に合わないので今回はsetを用いて愚直にシミュレーションして最後の個数を求める．

本問題では奇数個出てきた数字が残り，偶数個出てきた数字が残らないことがわかる．
そこでsetで集合管理をし，入力された数字がすでに集合内に含まれるときはその数を集合から削除する．入力された数が集合内に含まれないときはその数を集合に追加する．
最後に集合内に含まれている数値の数をカウントする．

setの宣言

set<long long> B;

今回は$ A_i $の最大値が$10^9$であることからlong long で宣言

set内への要素の追加

B.insert(挿入したい数)

set内からの要素の削除

B.erase(削除したい数)

set内の要素の検索

B.find(検索したい数)

今回は数の集合内の有無を調べた．

検索した数が集合内に含まれないときB.end()が返却される．

数値有無の判定部分

if(B.find(検索したい数)==B.end()){
    B.insert(検索したい数);
}

以上の処理で集合B内において入力された数の有無を確認し，集合内に数が存在しないとき集合に数を加えるという操作を行なっている．

解法コード

# include<bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<long long> A(N);
    set<long long> B;
    for(int i=0; i<N; i++){
        cin >> A.at(i);
        if(B.find(A.at(i))==B.end())
        {
            B.insert(A.at(i));
        }
        else
        {
            B.erase(A.at(i));
        }
    }
    cout << B.size() << endl;
}