Pythonで毎日AtCoder #36

はじめに

前回
今日は頭が動かなかったので、1問しか解いてません。

#36

ARC086-A

考えたこと
全ての要素の対してcountしているとTLEします。
countは使えないので、sortした後に隣り合う要素同士を比較していって要素の数を数えます。
要素の種類$set(a)$が$k$よりも多い場合は、$set(a)$から小さい順にansに足していきます。

n, k = map(int,input().split())
a = list(map(int,input().split()))

a.sort()
count = []
c = 1
for i in range(n-1):
    if a[i] != a[i+1]:
        count.append(c)
        c = 1
    else:
        c += 1
    if i == n - 2:
        count.append(c)

l = len(count)
#print(a)
#print(count)
c = 0
if l <= k:
    print(0)
else:
    count.sort()
    for i in range(l):
        l -= 1
        c += count[i]
        if l <= k:
            print(c)
            quit()

まとめ

countは遅い。(おそらく$O(N)$)。ではまた。