考えて競プロする

プログラミングコンテストの問題をどう考えて解いたかを記録していくブログです。使用言語はPython3

ABC022-B - Bumble Bee を解く(2)

ABC-B

ABC022-B - Bumble Bee を解く(1) の続き

提出したコードは TLE になってしまった

 

なぜ TLE になったのか？

 

# (種類ごとの数 -1)をカウント
c=0
for x in setl:
  c+=l.count(x)-1
 
おそらく for 文中で count 関数を呼び出しているためだと思われる
count はリスト内を全探索するので何度も呼び出すと時間がかかる
 
一回の探索で各数字の出現回数を把握したい。どうするか…？
 
前回の例を思い出してみる
 
{1,2,3,4,3,2,3,4,4,3,2,3}
 
どうすれば効率よく数えられるだろうか
…例えば、一度ソートしてみたらどうだろう？
 
{1,2,2,2,3,3,3,3,3,4,4,4}
 
上記のようにソートをした後なら
前から順に数えていくことで、各数が何個あるか数え上げることができる
 
問題で聞かれていることは、同じ種類の数の出現回数なので
前にある数と同じだったときだけ +1 カウントしていくようにすればいい
 
※カウントするタイミングのイメージ（前の数と同じときに +1 カウントする）
{1,2,2,2,3,3,3,3,3,4,4,4}
 
提出したコード
# 入力
N=int(input())

l=[]
for i in range(N):
  l.append(int(input()))

# ソート
l.sort()

c=0
for i in range(1,N):
  # 前の数と同じとき、+1する
  if l[i-1]==l[i]:
    c+=1

# 出力
print(c)
 

提出結果はACでした

 

解説を見るともっと簡単な解き方が紹介されていました

興味のある方は下記参照