概要

各生徒が誰か一人にプレゼントを渡すとき、誰にもプレゼントが届かなかった生徒の人数を求めます。

考察

この問題は、生徒 \(i\) がプレゼントを渡す相手 \(T_i\) が与えられ、逆に「誰からプレゼントを受け取ったか」を調べる問題です。

つまり、各生徒 \(j\) に対して、\(T_i = j\) となるような \(i\) の個数を数え、それが \(0\) であれば、生徒 \(j\) はプレゼントをもらえていないことがわかります。

素朴な方法として、各生徒 \(j\) について、すべての \(T_i\) を走査して \(T_i = j\) かどうかを確認する方法がありますが、これだと最悪の場合 \(N \times N = (2 \times 10^5)^2 = 4 \times 10^{10}\) 回の比較が必要となり、時間制限を超えてしまいます（TLE）。

そこで、与えられた配列 \(T\) の中で各生徒番号が何回出現するかを事前にカウントしておくことで、各生徒がプレゼントをもらった回数を高速に求めることができます。これは、Python の collections.Counter を使うと簡単に実現できます。

アルゴリズム

1. 各生徒がプレゼントを渡す相手のリスト \(T\) を読み込む。
2. Counter を使い、各生徒番号が \(T\) 中に何回出現するかをカウントする。
3. 出現回数が \(0\) である（誰からもプレゼントをもらってない）生徒の数を数える。
4. その数を出力する。

たとえば、入力が以下の場合：

4
2 3 4 2

これは、生徒 1 → 2、2 → 3、3 → 4、4 → 2 にプレゼントを渡していることを意味します。

このとき、 - 生徒 1：誰からももらってない（出現回数 0） - 生徒 2：生徒 1 と 4 からもらっている（出現回数 2） - 生徒 3：生徒 2 からもらっている（出現回数 1） - 生徒 4：生徒 3 からもらっている（出現回数 1）

よって、プレゼントが届かなかったのは生徒 1 のみで、答えは \(1\) です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• Counter を使うことで、各要素の出現回数を効率的に数えられる。
• インデックスは 1 から始まることに注意（生徒番号も 1 から \(N\)）。
• 高速な入出力処理（sys.stdin.read）を使用することで、大きな入力にも対応できる。

## ソースコード

```python
import sys
from collections import Counter

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

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

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。