概要

各生徒が「誰にプレゼントを渡したか」が与えられるので、誰からも渡されていない（=1つも受け取っていない）生徒の人数を数える問題です。

考察

各生徒はちょうど1人にプレゼントを渡します。つまり「生徒 \(i \rightarrow T_i\)」という有向辺を \(N\) 本持つグラフだと考えられます。

このとき、生徒 \(x\) がプレゼントを受け取った回数は、辺が \(x\) に向かって入ってくる本数（入次数）と一致します。
したがって「プレゼントを1つも受け取れない生徒」とは、入次数が \(0\) の頂点です。

素朴な方法が遅い理由

例えば「生徒 \(i\) が誰かから受け取っているか」を、生徒全員の \(T_j\) を調べて確認すると、 - 各 \(i\) について \(j=1..N\) を走査 → \(O(N)\) - これを \(N\) 人分 → 合計 \(O(N^2)\)

\(N \le 2 \times 10^5\) なので \(O(N^2)\) は到底間に合いません。

解決策

全員の \(T_i\) を1回だけ見て、受け取る側のカウント（入次数）を配列で増やしていけば、合計 \(O(N)\) で求められます。

具体例

\(N=4,\ T=[2,2,4,2]\) のとき、 - 2 は 1,4,? から計3回（実際は 1,2,4 から）受け取る → 入次数 3 - 4 は 3 から1回受け取る → 入次数 1 - 1 と 3 は誰からも受け取らない → 入次数 0

よって答えは 2 人です。

アルゴリズム

1. 長さ \(N+1\) の配列 indeg を用意し、すべて 0 で初期化する（1-indexed）。
2. 各 \(i=1..N\) について、indeg[T_i] += 1 として入次数を数える。
3. indeg[i] == 0 を満たす \(i=1..N\) の個数を数えて出力する。

計算量

• 時間計算量: \(O(N)\)（\(T_i\) を1回数え、最後に1回数えるだけ）
• 空間計算量: \(O(N)\)（入次数配列）

実装のポイント

• 添字を分かりやすくするため、indeg は N+1 要素にして生徒番号をそのまま index に使う（1-indexed）。

• 入力サイズが大きいので、Python では sys.stdin.buffer.read() を使うと安全に高速化できます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    T = data[1:]

    indeg = [0] * (N + 1)
    for t in T:
        indeg[t] += 1

    ans = 0
    for i in range(1, N + 1):
        if indeg[i] == 0:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。