ARC068 D Card Eater

所見

解説の方針頭良すぎワロタ

問題概要

N枚のカードに整数が書かれている。その中から任意の3枚を取り、最大の数と最小の数を食べ、カードの集合から同じ数がなくなることを目指す。最大で何枚残せるかを求めよ。

取った方針

同じ数が3枚以上あるとき、その3枚を選ぶことで同じ数を2枚減らすことができる。これを繰り返すと、M=奇数枚ある数はM/2回の操作のあと1枚に、L=偶数枚ある数はL/2-1回の操作のあと2枚になる。
同じ数が2枚あるとき、その2枚ともう一枚を選ぶことで1枚にすることができる。この時、もう一枚も"同じ数のカードが2枚ある数"を選ぶことで、同時に解決することができる。
よって、取る枚数は、2*(M/2 + L/2 - 1 + ceil(偶数枚ある数/2)) で求まる。

正しい方針(解説の方針)

この手順は、ほぼ任意のカードを捨てることができる。
Nは奇数である。
ここで、山の中にk種類の数があるとして、kが奇数ならば取り除かれるべきカードは偶数枚(奇数-奇数)あり、偶数ならば奇数枚ある。
よって、kが奇数ならば取り除かれるカードのみを取り除けるのでk、偶数ならば取り除かなくてもよいカードを1枚取り除かなくてはならないのでk-1となる。
コンテスト中にこれを思いついても本当に任意のカードを捨てられるかで悩んで選べなさそうな気がする。

得られた知見

・制約が与えられたとき、その制約は本当に考える必要があるかを考える(実はその制約がなくても同じ意味の操作、問題にならないか？)
・操作が与えられ、最適解を求めるとき、その操作で得られるもっとも効率のよい結果は何かを考える(貪欲をする)

解くのに必要な要素

・貪欲

周辺調査によって得られた知見

・ソート解法もある
・順番に意味がない問題の場合はソートを考えるとうまくいくこともある