C - Write and Erase

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 073
C - Write and Erase
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

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

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

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

制約

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

入力

入力は以下の形式で標準入力から与えられる。

N
A1
:
AN

出力

ゲーム終了後に紙に書かれている数字の個数を出力せよ。

解き方

以下を参考にしています。
https://img.atcoder.jp/abc073/editorial.pdf

解き方の流れ

まず、
「joisinoお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、書いていなければその数字を紙に書く」
という条件から
joisinoお姉ちゃんが
１回言った数字は紙に書かれる
２回言った数字は紙から消される
３回言った数字は紙に書かれる
４回言った数字は紙から消される
…
という流れになることが分かります。

ここから、
joisinoお姉ちゃんが
奇数回言った数字は紙に書かれ
偶数回言った数字は紙から消される
という法則を導くことができます。

そのため、
この問題は
Ai～ANで出てくる数字の出現回数を数え、
回数が奇数なら紙に書かれていると判断して答えの個数に加える、
回数が偶数なら紙に書かれていないと判断して答えの個数に加えない、
とすれば解けます。

実装する

数字の出現回数の数え方は、
Aiの範囲が「1≦Ai≦1000000000(=109)」なので
ここでは配列のindexを出現する数字とし、
配列の中身を出現回数として加算していくという方法がとれません。
（配列の添え字はint型なので溢れるindexはエラーになる）

そのため、
別の方法をとる必要があります。

配列を数字の小さい順に並び替え、
連続して出現する数字の個数を数えていき
別の数字が出てきたら
連続していた数字の出現した回数が
偶数か奇数かを求めて
奇数ならば最後に紙に書かれている数字とみなして
答えの個数に加えるという方法をとると解けます。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());

        var A = new long[N];
        for (int i = 0; i < N; ++i) A[i] = Int64.Parse(Console.ReadLine());
        //数字の小さい順に並び替え
        A = A.OrderBy(x => x).ToArray();

        //答えの個数をカウントする変数
        var ans = 0;
        //現在数えている数字
        var currentNum = 0L;
        //現在数えている数字の個数
        var currentNumCount = 0;

        //数字を数える
        for (int i = 0; i < N; ++i)
        {
            //現在数えている数字と配列の中身が同じものなら
            if (A[i] == currentNum)
            {
                //現在数えている数字の個数を加算する
                currentNumCount++;
            }
            //現在数えている数字と配列の中身が違うものなら
            else
            {
                //集計をする
                //現在数えている数字の個数が奇数の場合は答えに加算
                if (currentNumCount % 2 != 0) ans++;

                //情報を次の数字に書き換える
                //現在数えている数字を次の数字にする
                currentNum = A[i];
                //現在数えている数字の個数を１にリセット
                currentNumCount = 1;
            }
            //配列の最期の要素のみ、次の数字が来ることがないのでその場で集計する
            if (i == N - 1) if (currentNumCount % 2 != 0) ans++;
        }
        Console.WriteLine(ans);
    }
}