Problem:


Score : 600 points

Problem Statement

Takahashi has N cards. The i-th of these cards has an integer A_i written on it.

Takahashi will choose an integer K, and then repeat the following operation some number of times:

Choose exactly K cards such that the integers written on them are all different, and eat those cards. (The eaten cards disappear.)

For each K = 1,2, \ldots, N, find the maximum number of times Takahashi can do the operation.

Constraints

 1 \le N \le 3 \times 10^5 

 1 \le A_i \le N 

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print N integers.
The t-th (1 \le t \le N) of them should be the answer for the case K=t.

Sample Input 1

3
2 1 2

Sample Output 1

3
1
0

For K = 1, we can do the operation as follows:

Choose the first card to eat.

Choose the second card to eat.

Choose the third card to eat.

For K = 2, we can do the operation as follows:

Choose the first and second cards to eat.

For K = 3, we cannot do the operation at all. Note that we cannot choose the first and third cards at the same time.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

5
2
1
1
1

Sample Input 3

4
1 3 3 3

Sample Output 3

4
1
0
0



Sample input:
3
2 1 2


Sample output:
3
1
0

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A_ = [0] * (N+1)
for a in A:
    A_[a] += 1
A_ = sorted(A_)
c = 0
for i in range(N+1):
    A_[i] = c = A_[i] + c
A_.reverse()

Ans = [float("inf")] * (N+1)
for i in range(N):
    for j, a in enumerate(A_):
        d = a//(i+1)
        if Ans[i+j] > d:
            Ans[i+j] = d
        if d==0:
            break
    if j==0:
        for ii in range(i+1, N):
            Ans[ii] = 0
        break
del Ans[-1]
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

from collections import Counter

C=Counter(A)

LIST=sorted(C.values())
LEN=len(LIST)
SUM=sum(LIST)
BASE=[]
BASESUM=0

for k in range(1,N+1):
    if k>LEN:
        print(0)
    else:
        BASE.append(LIST[-k])
        #print(BASE)

        BASESUM+=LIST[-k]

        REST=SUM-BASESUM
        REST0=REST

        MIN=LIST[-k]
        MAX=LIST[-1]

        if MAX*k-BASESUM<=REST:
            print(SUM//k)
            continue

        while MIN!=MAX:
            mid=(MIN+MAX+1)//2
            REST=REST0

            for b in BASE[::-1]:
                if b<mid:
                    REST-=mid-b
                if REST<0 or b>=mid:
                    break

            #print(MAX,MIN,mid,REST)

            if REST>=0:
                MIN=mid
            else:
                MAX=mid-1

        print(MIN)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def f(k,p):
  acc = n 
  for i in range(len(b)):
    if b[i]>p:
      acc -= b[i]-p 
    else:
      break
  return (acc >= k*p)

n = inn()
a = inl()
h = {}
for x in a:
  if x in h:
    h[x] += 1
  else:
    h[x] = 1
b = []
for x in h:
  b.append(h[x])
b.sort(reverse=True)

#ddprint(b)

for k in range(1,n+1):
  mn = 0
  mx = n//k + 1
  while mx > mn+1:
    mid = (mn+mx)//2
    if f(k,mid):
      mn = mid 
    else:
      mx = mid 
  print(mn)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A_ = [0] * (N+1)
for a in A:
    A_[a] += 1
A_ = sorted(A_)
c = 0
for i in range(N+1):
    A_[i] = c = A_[i] + c
A_.reverse()

Ans = [float("inf")] * (N+1)
for i in range(N):
    for j, a in enumerate(A_):
        d = a//(i+1)
        if Ans[i+j] > d:
            Ans[i+j] = d
        if d==0:
            break
del Ans[-1]
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def f(k,p):
  acc = n 
  for i in range(len(b)):
    if b[i]>p:
      acc -= b[i]-p 
    else:
      break
  return (acc >= k*p)

n = inn()
a = inl()
h = {}
for x in a:
  if x in h:
    h[x] += 1
  else:
    h[x] = 1
b = []
for x in h:
  b.append(h[x])
b.sort(reverse=True)

#ddprint(b)

for k in range(1,n+1):
  mn = 0
  mx = n+1
  while mx > mn+1:
    mid = (mn+mx)//2
    if f(k,mid):
      mn = mid 
    else:
      mx = mid 
  print(mn)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
B = [-x for x in Counter(A).values()]
heapq.heapify(B)
for i in range(1, N+1):
    B_ = B[:]
    cnt = 0
    while len(B_) >= i:
        cnt += 1
        tmp = []
        for j in range(i):
            x = heapq.heappop(B_)
            if x < -1:
                tmp.append(x + 1)
        for b in tmp:
            heapq.heappush(B_, b)
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A_ = [0] * (N+1)
for a in A:
    A_[a] += 1
A_ = sorted(A_)
c = 0
for i in range(N+1):
    A_[i] = c = A_[i] + c
A_.reverse()

Ans = [float("inf")] * (N+1)
for i in range(N):
    for j, a in enumerate(A_):
        d = a//(i+1)
        #print(d, end=" ")
        Ans[i+j] = min(Ans[i+j], d)
        if d==0:
            break
    #print()
del Ans[-1]
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input()) 
L=list(map(int, input().split()))
c = collections.Counter(L)
fre = c.most_common()

for i in range(1,n+1):
  Lt = L[:]
  count = 0
  while True:
    c = collections.Counter(Lt)
    fre = c.most_common()
    if len(fre)<i:
      break
      
    else:
      count = count + 1
      for j in range(i):
        Lt.remove(fre[j][0])
        
  print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A_ = [0] * (N+1)
for a in A:
    A_[a] += 1
A_ = sorted(A_)
c = 0
for i in range(N+1):
    A_[i] = c = A_[i] + c
A_.reverse()

Ans = [float("inf")] * (N+1)
for i in range(N):
    for j, a in enumerate(A_):
        d = a//(i+1)
        #print(d, end=" ")
        Ans[i+j] = min(Ans[i+j], d)
        if d==0:
            break
    #print()
print("\n".join(map(str, Ans[:-1])))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

from collections import Counter

C=Counter(A)

LIST=sorted(C.values())
LEN=len(LIST)
SUM=sum(LIST)

for k in range(1,N+1):
    if k>LEN:
        print(0)
    else:
        BASE=LIST[-k:]
        #print(BASE)

        REST=SUM-sum(BASE)
        REST0=REST

        MIN=min(BASE)
        MAX=max(BASE)

        if MAX*k-sum(BASE)<=REST:
            print(SUM//k)
            continue

        while MIN!=MAX:
            mid=(MIN+MAX+1)//2
            REST=REST0

            for b in BASE:
                if b<mid:
                    REST-=mid-b
                if REST<0 or b>=mid:
                    break

            #print(MAX,MIN,mid,REST)

            if REST>=0:
                MIN=mid
            else:
                MAX=mid-1

        print(MIN)

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input()) 
L=list(map(int, input().split()))
c = collections.Counter(L)
fre = c.most_common()

for i in range(1,n+1):
  Lt = L[:]
  count = 0
  while True:
    c = collections.Counter(Lt)
    fre = c.most_common()
    if len(fre)<i:
      break
      
    else:
      count = count + 1
      for j in range(i):
        Lt.remove(fre[j][0])
        
  print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
An = [int(n) for n in input().split()]

for i in range(N):
    c = collections.Counter(An)
    cnt=0
    if len(c)<=i:
        print(cnt)
        continue
    while True:
        if c.most_common()[i][1]==0:
            break
        for j in c.most_common(i+1):
            c[j[0]] = c[j[0]]-1
        cnt +=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq

N = int(input())
A = list(map(int, input().split()))

c = collections.Counter(A)
x = [-i for i in c.values()]
#print(c)
#print(x)

# K = 1
print(N)

for K in range(2, N+1):
  if len(x) < K:
    print(0)
    continue
  cnt = 0
  q = x[:]
  heapq.heapify(q)
  while len(q) >= K:
    eat = []
    for k in range(K):
      eat.append(heapq.heappop(q))
    for e in eat:
      if e < -1:
        heapq.heappush(q, e + 1)
    cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
dic=[0]*(N+1)
for x in range(N):
	dic[A[x]]+=1
#dic.sort(reverse=True)
#print(dic)

for K in range(1,N+1):
	muda=0
	for x in dic:
		if x>(N//K):muda+=x-(N//K)
	print((N-muda)//K)

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq


def solve(cards):
    counter = collections.Counter(cards)

    counts = [(-count, card) for card, count in counter.items()]
    # Max heap
    heapq.heapify(counts)

    for k in range(1, len(cards) + 1):
        times = 0
        heap = counts.copy()
        while heap:
            if len(heap) < k:
                break
            to_remove = [heapq.heappop(heap) for _ in range(k)]
            for e in to_remove:
                count, card = e
                count = - count - 1
                if count == 0:
                    continue
                heapq.heappush(heap, (-count, card))
            times += 1
        print(times)


if __name__ == "__main__":
    n = int(input())
    a_s = [int(l) for l in input().split(' ')]
    solve(a_s)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

from collections import Counter

C=Counter(A)

LIST=sorted(C.values())
LEN=len(LIST)
SUM=sum(LIST)

for k in range(1,N+1):
    if k>LEN:
        print(0)
    else:
        BASE=LIST[-k:]
        #print(BASE)

        REST=SUM-sum(BASE)
        REST0=REST

        MIN=min(BASE)
        MAX=max(BASE)

        if MAX*k-sum(BASE)<=REST:
            print(SUM//k)
            continue

        while MIN!=MAX:
            mid=(MIN+MAX+1)//2
            REST=REST0

            for b in BASE:
                if b<mid:
                    REST-=mid-b

            #print(MAX,MIN,mid,REST)

            if REST>=0:
                MIN=mid
            else:
                MAX=mid-1

        print(MIN)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
dic=[0]*(N+1)
for x in range(N):
	dic[A[x]]+=1
dic.sort(reverse=True)
#print(dic)

for K in range(1,N+1):
	muda=0
	for x in dic:
		if x>(N//K):muda+=x-(N//K)
	print((N-muda)//K)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
c = Counter(map(int, input().split()))
orig = [v[1] for v in c.most_common()]
l = len(orig)

def solve(l, num):
  ans = 0
  while True:
    l.sort()
    for i in range(-1, -(num + 1), -1):
      if l[i] == 0:
        print(ans)
        return

      l[i] -= 1
      
    ans += 1

for i in range(1, n + 1):
  if l < i:
    print(0)
  else:
    solve(orig.copy(), i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
a_set = set(a_list)
i = 0
duplicates = []
for ai in a_set:
    duplicates.append(len([a for a in a_list if a == ai]))
for k in range(1, len(a_set)+1):
    times = 0
    dup = duplicates[:]
    while True:
        dup.sort(reverse=True)
        if(dup[k-1] == 0):
            break
        for i in range(k):
            dup[i] -= 1
        times += 1
    print(times)
for i in range(n - len(a_set)):
    print("0")

Submission status: Time Limit Exceeded

Solution code:
#"""
import sys
input = sys.stdin.readline
#"""

N = int(input())
*A, = map(int,input().split())

import heapq

B = {}
for a in A:
    B[a] = B.get(a,0)+1

B= sorted([-b for b in B.values()])
heapq.heapify(B)
M = len(B)
B2 = B[:]

for k in range(1,N+1):
    B = B2[:]
    if k>M:
        print(0)
        continue
    elif k==M:
        print(-max(B))
    else:
        ans = 0
        while True:
            C = [-heapq.heappop(B) for _ in [0]*k]
            m = -B[0]
            cnt = min((C[-1]-m)+1,C[-1])
            for c in C:
                heapq.heappush(B,-(c-cnt))
            ans += cnt
            if cnt==0 : break
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = sorted(list(map(int, input().split())))
Ts = []
Os = 0
c = 1
for i in range(1, N):
    if As[i - 1] != As[i]:
        Ts.append(c)
        c = 1
    else:
        c += 1
Ts.append(c)
Ts.sort(reverse=True)
import copy

for K in range(1, N + 1):
    c = 0
    Tsc = copy.copy(Ts)
    while (True):
        L = len(Tsc)
        if L < K:
            break
        else:
            t = Tsc[K - 1]
            c += t
            for i in range(K):
                Tsc[i] -= t
            Tsc.sort(reverse=True)
            while (True):
                l = len(Tsc)
                if l == 0:
                    break
                if Tsc[l - 1] == 0:
                    Tsc.pop()
                else:
                    break
            pass
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq


def solve(cards):
    counter = collections.Counter(cards)

    counts = [(-count, card) for card, count in counter.items()]
    # Max heap
    heapq.heapify(counts)

    ans = [0] * len(cards)
    for k in range(1, len(cards) + 1):
        times = 0
        heap = counts.copy()
        while heap:
            if len(heap) < k:
                break
            to_remove = [heapq.heappop(heap) for _ in range(k)]
            for e in to_remove:
                count, card = e
                count = - count - 1
                if count == 0:
                    continue
                heapq.heappush(heap, (-count, card))
            times += 1
        ans[k - 1] = times

    return ans


if __name__ == "__main__":
    n = int(input())
    a_s = [int(l) for l in input().split(' ')]
    for ans in solve(a_s):
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(input())
a = [int(i) for i in input().split()]
b = {}
for i in a:
    if i in b:
        b[i] += 1
    else:
        b[i] = 1
c = [-b[i] for i in b]
heapq.heapify(c)


def take(k, a):
    a = a[:]
    b = []
    for _ in range(k):
        if len(a) == 0:
            return -1
        c = heapq.heappop(a)
        if c == 0:
            return - 1
        heapq.heappush(b, c + 1)
    while a:
        c = heapq.heappop(a)
        heapq.heappush(b, c)
    return b


for k in range(1, n+1):
    l = 0
    d = c[:]
    while True:
        d = take(k, d)
        if d == -1:
            print(l)
            break
        l += 1

Submission status: Time Limit Exceeded

Solution code:
import copy

def ans(l,K):
    if len(l)<K:
        return 0
    res=0
    lc=l.copy()
    while lc[K-1]>0:
        for i in range(K):
            lc[i]-=1
        lc.sort(reverse=True)
        res+=1
    return res

N=int(input())
A=list(map(int,input().split()))

d={}
for Ai in A:
    if Ai not in d:
        d[Ai]=1
    else:
        d[Ai]+=1

l=list(d.values())
l.sort(reverse=True)

for K in range(1,N+1):
    print(ans(l,K))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

C = [0] * N
D = [0] * (N + 1)
for a in A:
    C[a - 1] += 1
    D[C[a - 1]] += 1

S = [0] * (N + 1)
for i in range(N):
    S[i + 1] = S[i] + D[i + 1]

ans = N
for K in range(1, N + 1):
    while ans > 0 and S[ans] < K * ans:
        ans -= 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
とりあえず，数字ではなく，数字の出現回数C[i]を持つ．

Kが変化すると色々と変わるので，Kごとに見ようとすると割と大変そう，1つのkごとにO(N)すらかけられない，というか計算大変そう．
(カードがT種類あるとして，k>Tは全部0だったりする．Kの区間に対して一気に答えを出す方法はありそう．)

食べる回数をmとして，mごとに最大のKを求める．

m回食べるということは，各数字につき最大m回までしか食べられないということ
食べられる枚数の総数はΣ(min(m,C[i]))．このときの最大のKは，総数//m

C[i]を昇順に並べておけば二分探索で
min(m,C[i])=C[i]の範囲がわかり，累積和をとっておればこの区間の合計がO(1)で求まる
"""
def main():
    import bisect
    
    N=I()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(N):
        dd[A[i]]+=1
        
    L=[]
    for k,v in dd.items():
        L.append(v)
        
    L.sort()
    nl=len(L)
    S=[0]*(nl+1)
    for i in range(nl):
        S[i+1]=S[i]+L[i]
        
    ans=[0]*(N+1)
    
    for m in range(1,N+1):
        temp=0
        num=bisect.bisect_left(L,m)
        temp+=S[num]
        temp+=(nl-num)*m
        
        maxk=temp//m
        ans[maxk]=max(ans[maxk],m)
        # print(m,temp,maxk)
        
    # print(ans)
        
    M=0
    for i in range(N,-1,-1):
        M=max(M,ans[i])
        ans[i]=M
        
    for i in range(1,N+1):
        print(ans[i])
        
        
        
    
    

main()

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
d = defaultdict(lambda: 0)
for a in A:
    d[a] += 1
cant_use = [0] * (N+1)
for v in d.values():
    for i in range(v):
        cant_use[i] += v - i


def is_ok(i, k):
    return (N-cant_use[i])/k >= i

def bisect(ng, ok, k):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, k):
            ok = mid
        else:
            ng = mid
    return ok

for k in range(1, N + 1):
    print(bisect(N+1, 0, k))

Submission status: Accepted

Solution code:
from collections import Counter
import bisect


def main():
    N = int(input())
    A = list(map(int, input().split()))
    count_list = list(Counter(A).values())
    count_list.sort()
    cumsum_count = [0] * len(count_list)
    cumsum_count[0] = count_list[0]
    for i in range(1, len(count_list)):
        cumsum_count[i] = cumsum_count[i - 1] + count_list[i]
    ans_list = [0] * N
    n_max = N
    for k in range(1, len(count_list) + 1):
        # 最大でも N // k 回まで。
        # 各カード n_max 枚まで使って k * n_max の長方形領域を全部埋め尽くせるかを調べる。
        # 埋め尽くせる最小の n_max が答え。
        n_max = min(n_max, N // k)
        s = 0
        while True:
            # n_max 枚以上あるカードは n_max 枚固定
            index = bisect.bisect_left(count_list, n_max)
            s = n_max * (len(count_list) - index)
            # それ未満のカードはそのまま全部使う
            if index > 0:
                s += cumsum_count[index - 1]
            if s >= k * n_max or n_max == 0:
                break
            n_max -= 1
        ans_list[k - 1] = n_max
    for ans in ans_list:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = [0] * (N+1)
    Cnt_A = [0] * (N+1)
    for a in A:
        Cnt_A[a] += 1
        cnt = Cnt_A[a]
        C[cnt] += 1
    cum_C = []
    cu = 0
    for c in C:
        cu += c
        cum_C.append(cu)
    Ans = []
    for k in range(1, N+1):
        # K = k のとき、 n 組以上作れる <=> 使えるカードが nk 枚以上
        # n 組以上作れる <=> 同じカードは n 枚以下
        # 同じカードは n 枚以下で全体として nk 枚以上用意できるか？
        ok, ng = 0, N//k+1
        while ok + 1 < ng:
            n = ok+ng>>1
            if cum_C[n] >= n*k:
                ok = n
            else:
                ng = n
        Ans.append(ok)
    print("\n".join(map(str, Ans)))

main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = list(Counter(a).values())
c.sort()

ans = n
cnt = 0
for i in range(n):
    m = i + 1 - cnt
    while c and c[-1] > ans // m:
        ans -= c.pop()
        cnt += 1
        m -= 1
    print(ans // m)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
D = [0]*(n+1)
for v in C.values():
  D[v] += 1
E = tuple(accumulate(k*d for k, d in enumerate(D)))
D = tuple(accumulate(D))
F = [0]*(n+1)
for x in range(1, n+1):
  temp = (E[x] + x*(D[n]-D[x])) // x
  F[x] = temp
for k in range(1, n+1):
  ok = 0
  ng = n+1
  while ng-ok > 1:
    mid = (ok+ng)//2
    if k <= F[mid]:
      ok = mid
    else:
      ng = mid
  print(ok)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
cnt = [0]*(N+1)
B = [0]*(N+1)

for Ai in A:
    cnt[Ai] += 1
    B[cnt[Ai]] += 1

acc = [0]

for Bi in B:
    acc.append(acc[-1]+Bi)

x = N

for K in range(1, N+1):
    while x>0 and K*x>acc[x+1]:
        x -= 1
    
    print(x)

Submission status: Accepted

Solution code:
from bisect import *
N=int(input())
A=list(map(int,input().split()))
B=[0]*(N+1)
for i in range(N):
  B[A[i]]+=1
C=[0]*(N+1)
for i in range(N+1):
  C[B[i]]+=1
D=[0]
E=[0]
for i in range(N+1):
  D.append(D[i]+i*C[i])
  E.append(E[i]+C[-i-1])
E=E[::-1]
F=[]
for i in range(1,N+1):
  F.append((D[i+1]//i)+E[i+1])
F=F[::-1]
for i in range(N):
  print(N-bisect_left(F,i+1))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))

    # C[x]: 書かれている整数がxであるカードの枚数
    C = [0] * (N + 1)
    D = [0] * (N + 1)
    for a in A:
        C[a] += 1
        D[C[a]] += 1

    # AからK(1<=K<=N)枚ずつカードを抜いてったときに、
    # x回以上抜くことができるか判定する。
    # 抜くことができると判定されたxの最大値が答えになる。

    # 例えば、A = [1 1 1 1 1 2 2 3] とする。
    # -> C = [5 2 1 0 0 0 0 0]
    # ここから2枚ずつカードを抜ける回数を考えるとき、
    # 「3回抜く」とすると、数字の1は、どうやっても2個は絶対余る
    # そこで、絶対余る部分を捨ててCを作り直す(=Eとする)と、
    # E = [3 2 1 0 0 0 0 0]
    # ここから2枚ずつ3回抜けるか判定するなら、
    # sum(E) >= 2 * 3 = 6
    # であるか見ればよい。今回の場合ちょうど6なので、2枚ずつ3回は抜ける。
    
    # 3枚ずつ2回ぬけるか調べる場合、
    # E = [2 2 1] となり、sum(E) = 5 < 3 * 2 = 6 なので、抜けないことが分かる

    # よって、
    # sum(min(C[i], x)) >= K * x であれば抜くことができる
    # S(x) = sum(min(C[i], x)) とすると、
    # S(x) = S(x-1) + [Cの中でC[i] >= x であるものの個数]
    # となることから、Cの中でC[i] >= x であるものの個数 = D(x) とすると、
    # S(x) = sum_(1~x) D(i) となる。
    # つまり、S(x)は、D(x) を最初に全部計算しておいて、累積和をとることで高速に計算できる。

    # S(x) >= K * x となるxの最大値を、kを1からNまで動かして見つければよい。
    # ここで、xを左辺にもっていって、
    # S(x) / x >= Kとなるxの最大値を見つけるようにする。
    # また、S(x) / x = f(x) とおく。

    # 最大値を見つけるために2分探索してもいいが、
    # Kが増えると、答えは以前の値以下になるはずなので、
    # K+1のとき、Kでの答えの位置から0へと探索していけば、O(N)で答えが見つかる
    S = [0] * (N + 1)
    f = [0] * (N + 1)
    for x in range(1, N+1):
        S[x] = S[x-1] + D[x]
        f[x] = S[x] // x

    ans = []
    prev_ans = N
    for K in range(1, N+1):
        a = prev_ans
        while True:
            if f[a] >= K or a == 0:
                break
            a -= 1
        ans.append(a)
        prev_ans = a

    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
c = Counter()
for x in a: c[x] += 1
cv = Counter()
for v in c.values(): cv[v] += 1
#print(cv)

def check(x, K):
  t = 0
  for k, v in cv.items(): t += min(k, x) * v
  return t >= K * x

res = [N] * (N + 1)
for K in range(1, N):
  ok = 0
  ng = res[K] + 1
  while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m, K + 1): ok = m
    else: ng = m
  res[K + 1] = ok

for r in res[1: ]: print(r)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
k = sorted(map(int, input().split()))

hist = []
count = 0
for i in range(n):
    count += 1
    if i == n - 1 or k[i] != k[i + 1]:
        hist.append(count)
        count = 0
hist.sort()

sumh = [0]
for i in range(len(hist)):
    sumh.append(sumh[-1] + hist[i])

def ok(h, d):
    i = bisect.bisect_left(hist, h)
    s = sumh[i] + h * (len(hist) - i)
    return s >= h * d

def binary_search(d):
    lo, hi = 0, n // d + 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if ok(mid, d):
            lo = mid
        else:
            hi = mid
    return lo

for d in range(1, n + 1):
    print(binary_search(d))

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    from collections import Counter as ct
    from bisect import bisect_left as bl

    n = int(input())
    max_a = sorted(ct(list(map(int, input().split()))).values())
    now_a = [i for i in max_a]
    m = len(max_a)
    cnt = m
    ans = 0
    ans_list = [0]*(n-m)

    for use in range(m, 1, -1):
        rest = ans
        nex = now_a[0]
        while rest:
            val = nex
            start = bl(now_a, val+1)
            nex += 1
            q = max(-1, start-1-rest, bl(max_a, now_a[start-1]+1)-1)
            for i in range(start-1, q, -1):
                now_a[i] += 1
            if now_a[start-1] == 1:
                cnt += start-1-q
            rest -= start-1-q
            if start != m:
                nex = now_a[start]
        while cnt >= use:
            ans += 1
            rest = use
            nex = now_a[-1]
            end = m
            while rest:
                val = nex
                start = bl(now_a, val)
                if start != 0:
                    nex = now_a[start-1]
                end = min(end, bl(now_a, val+1), start+rest)
                for i in range(start, end):
                    now_a[i] -= 1
                if now_a[start] == 0:
                    cnt -= end-start
                rest -= end-start
                end = start
        ans_list.append(ans)
    print(n)
    for i in ans_list[::-1]:
        print(i)


main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    from collections import Counter as ct
    from bisect import bisect_left as bl

    n = int(input())
    max_a = sorted(ct(list(map(int, input().split()))).values())
    now_a = [i for i in max_a]
    m = len(max_a)
    cnt = m
    ans = 0
    ans_list = [0]*(n-m)

    for use in range(m, 1, -1):
        rest = ans
        nex = now_a[0]
        while rest:
            val = nex
            start = bl(now_a, val+1)
            nex += 1
            q = max(-1, start-1-rest, bl(max_a, now_a[start-1]+1)-1)
            for i in range(start-1, q, -1):
                now_a[i] += 1
            if now_a[start-1] == 1:
                cnt += start-1-q
            rest -= start-1-q
            if start != m:
                nex = now_a[start]
        while cnt >= use:
            ans += 1
            rest = use
            nex = now_a[-1]
            end = m
            while rest:
                val = nex
                start = bl(now_a, val)
                if start != 0:
                    nex = now_a[start-1]
                end = min(end, bl(now_a, val+1), start+rest)
                for i in range(start, end):
                    now_a[i] -= 1
                if now_a[start] == 0:
                    cnt -= end-start
                rest -= end-start
                end = start
        ans_list.append(ans)
    print(n)
    for i in ans_list[::-1]:
        print(i)


main()

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    m = max(list(Counter(A).values()))
    d = Counter(Counter(A).values())
    l = []
    t = 0
    for i in range(m, 0, -1):
        t += d[i]
        l.append(t)
    l.reverse()
    t = 0
    r = []
    for i in range(N):
        if m > i:
            t += l[i]
        r.append(t//(i+1))
    p = -1
    a = []
    for i, v in enumerate(reversed(r)):
        if p != v:
            a.append((v, N-i))
        p = v
    a.append((N, 0))
    t = 0
    aa = []
    for i in range(1, N+1):
        if a[t][0] < i:
            t += 1
        aa.append(a[t][1])
    for i in aa:
        print(i)
main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
C = [0] * (N + 1)
for a in A:
    C[a] += 1
D = [0] * (N + 1)
for c in C:
    D[c] += 1
P = [0] * (N + 1)
Q = [0] * (N + 1)
for i in range(1, N+1):
    P[i] = P[i-1] + i * D[i]
    Q[i] = Q[i-1] + D[i]
F = [0] * (N + 1)
for i in range(1, N+1):
    F[i] = int((P[i] + i * (Q[N] - Q[i])) / i)
index = N
for i in range(1, N+1):
    while True:
        if index == 0:
            print(0)
            break
        if F[index] >= i:
            print(index)
            break
        else:
            index -= 1

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**7)
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))

from collections import Counter
from itertools import accumulate
import bisect

n = readint()
a = readints()
b = sorted(Counter(a).values())
exist = len(b)
b = [0]*(n-exist)+b
c = list(accumulate([0]+b))

ans = [n]
for k in range(2,exist+1):
    l = 0
    r = n//k+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    ans.append(l)

printrows(ans+[0]*(n-exist))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))

from collections import Counter
from itertools import accumulate
import bisect

n = readint()
a = readints()
b = sorted(Counter(a).values())
exist = len(b)
b = [0]*(n-exist)+b
c = list(accumulate([0]+b))

ans = [n]
for k in range(2,exist+1):
    l = 0
    r = n//k+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    ans.append(l)

printrows(ans+[0]*(n-exist))

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate
import bisect

printRows = lambda x:print('\n'.join(map(str,x)))

n = int(input())
a = list(map(int, input().split()))
b = sorted(Counter(a).values())
exist = len(b)
b = [0]*(n-exist)+b
c = list(accumulate([0]+b))

ans = [n]
for k in range(2,exist+1):
    l = 0
    r = n//k+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    ans.append(l)

printRows(ans+[0]*(n-exist))