ABC073 C - Write and Erase

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    ret = set()
    for n in range(N):
        i = [ii()]
        ret ^= set(i)
    print(len(ret))


if __name__ == '__main__':
    main()

考え方

紙に対して、N回数字を加えるが、

  • すでに同じ数字が存在する場合には数字を消す
  • 数字が存在していない場合には数字を加える

というルールが存在している。

この条件はXORで簡単に満たすことができる。
紙に書かれている数字とこれから紙に加える数字のXORをN回行うことによって、
回答を得ることが出来る。