✨

ARC068 D - Card Eater解説[python]

2021/01/09に公開

URL

3<=N<=10^{5}

Nは奇数

1<=ai<=10^{5}

n = int(input())
a = list(map(int, input().split()))
duplicate = n - len(set(a))
cnt = (duplicate + 1) // 2
print(n - 2 * cnt)

全て異なる値にすることは可能なことの証明
- 同じ値のカードが3枚以上ある時、その値のカードを3枚選ぶと2枚消すことができる
- 2枚ある時は、その二枚とそれ以外のカードを一枚選べば1枚消すことができる
- よって奇数枚ある限り全て異なる値にすることは可能
操作回数を最小にするためには、元々重複のない値のカードを消す回数を少なくすること
- 全体のカード数　- その中のUniqueな値の数 = duplicate　とすると
- 全ての操作で重複のあるカードのみ消すことができると操作回数はduplicate/2 となり、これが最小（可能なら）
- 不可能な状況を考えると、同じ値が複数枚あるカードが1種類しかなく、かつその枚数が二枚の時　のみである。
- よって元々重複のない値のカードを消す回数は高々一回となる。