ARMERIA

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

AtCoder Beginner Contest 143 F - Distinct Numbers

AtCoder プログラミング競技プログラミング

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$ 個以下取ろうとすると、

$B_{i} \lt n$ であるような $B_{i}$ については全て取る。
$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