ABC143F - Distinct Numbers

ABC227Dと内容はほとんど同じですが，計算を効率的にしなければなりません．
【類題】

• D - Project Planning (ABC227D - Project Planning - 競プロはじめました)

方法1

考え方

まず，整数$a$が何回出てきたかをカウントすると，ABC227Dと同じ問題になる．ただし，今回は$N$回計算しなければならない．

与えられた$\{A_{i}\}$は座標圧縮して，カウント結果をcntというリストで表す．

$O(N)$の計算

\begin{aligned}
\sum_{i \in S} \min(x, \mathrm{cnt}[i])
\end{aligned}

を$N$回計算すると，最悪$O(N^{2})$でTLEする．したがって，この和をもっと効率的に計算しなければならない．

cntをソートすると，ind = min(bisect_left(cnt, x), len(cnt))に対して

\begin{aligned}
& \sum_{i \in S} \min(x, \mathrm{cnt}[i]) \\
&= \sum_{0 \leq i\leq \mathrm{ind}} \mathrm{cnt}[i] + \sum_{i > \mathrm{ind}} x\\
&= \sum_{0 \leq i \leq \mathrm{ind}} \mathrm{cnt}[i] + x (|S| - \underbrace{(\mathrm{ind} + 1)}_{\hspace{-5em}\mathrlap{\text{第1項で和を取った個数}}})
\end{aligned}

となる．よって，cntの累積和が計算できていれば，和は$O(1)$で計算できる．

あとはABC227Dと同じように二分探索で

\begin{aligned}
\sum_{i \in S} \min(x, \mathrm{cnt}[i])
\geq x \cdot K
\end{aligned}

となる最大の$x$を求めれば良い．

$K = 1,2, ..., N$に対して二分探索を2回行うので，$O(N (\log N)^{2})$で解けた．

回答例

from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))
D = {a:i for i, a in enumerate(sorted(list(set(A))))}

cnt = [0] * len(D)
for a in A:
  cnt[D[a]] += 1
cnt.sort()

acc = [0] * (len(D) + 1)
for i in range(len(D)):
  acc[i + 1] = acc[i] + cnt[i]
  
def my_sum(x):
  ind = min(bisect_left(cnt, x), len(D))
  return acc[ind] + x * (len(D) - ind)
  
def check(K, x):
  if K * x <= my_sum(x):
    return True
  else:
    return False

for K in range(1, N + 1):
  ok = 0
  ng = 10 ** 6
  while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(K, mid):
      ok = mid
    else:
      ng = mid
  print(ok)

方法2

考え方

上で，よく考えれば累積和ではなく

\begin{aligned}
& \sum_{i \in S} \min(x, \mathrm{cnt}[i]) \\
&= \sum_{0\leq i \leq \mathrm{ind}} \mathrm{cnt}[i] + x (|S| - (\mathrm{ind} + 1))
\end{aligned}

自体を予め（ループの外で）計算できる（$O(N)$）．

よって，全体の計算量は$O(N \log N)$となる．

回答例

N = int(input())
A = list(map(int, input().split()))
D = {a:i for i, a in enumerate(sorted(list(set(A))))}

cnt = [0] * len(D)
for a in A:
  cnt[D[a]] += 1
cnt.sort()

SUM = [0] * (10 ** 6 + 1)
acc = 0
used = 0
for x in range(10 ** 6 + 1):
  while used < len(cnt) and cnt[used] <= x:
    acc += cnt[used]
    used += 1
  SUM[x] = acc + x * (len(cnt) - used)
  
def check(K, x):
  if K * x <= SUM[x]:
    return True
  else:
    return False

for K in range(1, N + 1):
  ok = 0
  ng = 10 ** 6
  while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(K, mid):
      ok = mid
    else:
      ng = mid
  print(ok)

方法3

考え方

さらに，二分探索も省略することができる．

各$K$に対し

\begin{aligned}
\sum_{i \in S} \min(x, \mathrm{cnt}[i])
\geq x \cdot K
\end{aligned}

を満たす最大の$x$を求める問題は，各$K$に対し

\begin{aligned}
\biggl\lfloor \frac{\sum_{i \in S} \min(x, \mathrm{cnt}[i])}{x} \biggr \rfloor
\geq K
\end{aligned}

を満たす最大の$x$を求める問題に置き換えられる（$K$は非負整数）．

「方法2」を書き換えることで，左辺は予め計算できる．

また，左辺は$x$について単調減少だから，$x$を順に見ていけば$O(N)$で$K=1,2...,N$に対して上の条件を満たす最大の$x$を探索できる．

回答例

N = int(input())
A = list(map(int, input().split()))
D = {a:i for i, a in enumerate(sorted(list(set(A))))}

cnt = [0] * len(D)
for a in A:
  cnt[D[a]] += 1
cnt.sort()

SUM = [0] * (10 ** 6 + 1)
acc = 0
used = 0
for x in range(1, 10 ** 6 + 1):
  while used < len(cnt) and cnt[used] <= x:
    acc += cnt[used]
    used += 1
  SUM[x] = (acc + x * (len(cnt) - used)) // x

x = 0
ans = [0] * N
for K in range(N, 0, -1):
  while SUM[x + 1] >= K:
    x += 1
  ans[K - 1] = x
print(*ans, sep = '\n')