Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

ABC143-F Distinct Numbers

atcoder.jp

概要

最大30万枚のかーどがあたえられ、一枚のカードにはそれぞれ1~30万の数字がある。あなたはこの中からK枚のカード選び、それらを取り除く。この操作は何回できるだろうか?ただし、Kは1からNまですべて試しそれぞれ出力すること。

ACするまで

1. x回操作できることの条件を考える。 \sum_{i=1}^{N}{min(E_i, x)} >= Kxが条件。ただし、[tex; E_i]はi個の同じものを持つカードの数。
2. 上のものを愚直に計算すると O(N)、二分探索とかをしても間に合わない! -> 何とかして落とす
3.  \sum_{i=1}^{N}{min(E_i, x)}差分に着目!なんか差分ならばうまく前計算すれば定数時間で追えそう。
4. 実装->AC!

考察

この問題のこの解法はけんちょんさんなどと本質的には同じな気がするが、より簡潔である。

ACするまでにモデリングした式を差分で計算することを考える。ちなみにあの式の意味は、x回とるとき、カードの枚数がx以下の時はそのまますべて使える、x回より大きいならx枚までしか使えない。そしてそれらの合計が Kx以上でないならばどう頑張っても作れない。逆に以上ならば作れる。

ひとまず、合計を、min関数によって E_iが蓋される方( E_i>x)と、されてないほう( E_i <= x)に分ける。
前者は、xが1減るごとに、 E_x分だけ増える。(xが1減ると、E_x種類のカードが蓋される)。これは累計を取って置けばよい。ちなみに最終的に計算する際は、累計に現時点のXを掛ければよい。

後者は、xが1減るごとに、 E_x*xだけ減る。(xが1減ると、E_x*x枚の数だけ蓋されてないものの合計が減る。)

これをもとに二分探索すればよいが、さらにオーダーを落とせる。

Kの増加に従って、xは広義単調減少する。
よって、わざわざ二分探索する必要すらなく、しゃくとり法の要領で単調に決定することができて、計算量は O(N)

ACコード:
Submission #8336000 - AtCoder Beginner Contest 143

一言

自分で考え出す綺麗な実装って気持ちいい。