ARC068 D - Card Eater解説[python]

1 min read読了の目安(約800字

URL

https://atcoder.jp/contests/arc068/tasks/arc068_b

問題概要

  • N枚のカードがあり操作を行うことで操作後に残った全てのカードの値が異なるようにしたい
  • 最小の操作回数を答えよ
  • 操作:任意の3枚を選び、その中で最大値と最小値を消す

制約

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種類しかなく、かつその枚数が二枚の時 のみである。
    • よって元々重複のない値のカードを消す回数は高々一回となる。

実装方針

  • (全体のカード数 - その中のUniqueな値の数 = duplicate) を計算して2でわる。
  • duplicateが2で割って1余る時は切り上げ
  • 残った枚数は操作回数*2をnからひく

次回への反省

参考