ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 143 F - Distinct Numbers

F - Distinct Numbers

解法

色々な解法があるみたいですが…この記事ではそれぞれの  K について独立に解きます。ある  K について解くときには、可能な操作回数には単調性があるので二分探索できます。

ある  K と操作回数  n を固定したときに、操作を  n 回行えるかどうか判定する方法を考えます。まず  nK \le N は必ず満たす必要があります。その上で  \lbrace A_{i}\rbrace の中から使う整数を  nK 個選んで

(*) 全部で  nK 個の整数から、「異なる  K 個の整数を取り除く」という操作を  n 回行うことができる

かどうかを判定したいです。このとき(*)の必要十分条件として、

全ての整数値  v について、 nK 個の中に  v が含まれる個数は  n 個以下である

というものがあります。

必要性については、もし  n 個を超える整数値が存在する場合はそれらを  n 回の操作で全て取り除くことができないことから示せます。

十分性については、以下のようにすると実際に構成できることから示せます。(Special Thanks:てんぷらさん

f:id:betrue12:20191020000241p:plain

つまり  \lbrace A_{i}\rbrace から各整数値を  n 個以下取ってきて、合計で  nK 個確保できればOKということになります。これは以下のように解くことが出来ます。

まず  \lbrace A_{i}\rbrace を「整数値○が  B_{1} 個、整数値△が  B_{2} 個…」という風に集計したときの数列  \lbrace B_{i}\rbrace を求めて、これをソートしておきます。このとき各整数値を  n 個以下取ろうとすると、

  1.  B_{i} \lt n であるような  B_{i} については全て取る。
  2.  B_{i} \ge n であるような  B_{i} についてはそれぞれ  n 個ずつ取る。

ということになります。1.と2.の境界を二分探索などで求めて、1.については累積和を求めておくと、取れる個数の合計を効率的に求めることが出来ます。これが  nK 以上かどうか判定すれば良いです。

この解法だと全ての  K を試すので  O(N)、答えを求めるための二分探索で  O(\log N) B_{i} \lt n を満たす境界を求めるのに  O(\log N) で、全体  O(N(\log N)^{2}) になります。ちょっと重いですね。 B_{i} \lt n を満たす境界を全ての  n について前計算しておくと  \log が1個落ちるなど、計算量の改善は色々あると思います。

ACコード

Submission #8035553 - AtCoder Beginner Contest 143