python3の時間短縮の方法

Question

N人の社員からなる会社があり、各社員には 1…N の社員番号が割り当てられています。
社員番号 1 の社員以外の全ての社員には、自分より社員番号が小さい直属の上司がちょうど 1 人います。

Xさんが Yさんの直属の上司であるとき、Y さんは X さんの直属の部下であるといいます。
社員番号 iの社員の直属の上司の社員番号が Aiであることが与えられます。各社員について直属の部下が何人いるか求めてください。

N=input()
A=input().split()
Al=list(A)
a=0
for a in range(int(N)):
  a=a+1
  b=(Al.count(str(a)))
  if b>0:
    print(b)
  else:
    print(0)

Atcoderの上記のような問い(https://atcoder.jp/contests/abc163/tasks/abc163_c)で上記のようなコードを書いたのですが、実行時間超過してしまいました。どこをどう言った風に変えると時間短縮が可能ですか。

Answer 1

list.countは要素を先頭から逐次探索するので、O(n)です。
for文内にそれを埋め込むと、全体ではO(n^2)になります。

辞書を用意して Ai を集計していけば良いでしょう。
集計はO(n)で、求解はそれぞれがO(1)なので全体ではやはりO(n)で実行できます。

コードの貼り方について

teratailには、コードを見やすく表示する機能があります。
質問編集画面を開き、コードを選択した状態で<code>ボタンを押して下さい。

特にPythonの場合、インデントが崩れるとコードの意味が変わってしまいます。

---

また問題を引用するのであれば、引用元のリンクを貼るようにして下さい。