概要

\(N\) 人の生徒がそれぞれ1人を指名してプレゼントを渡したとき、誰からもプレゼントをもらえなかった生徒の人数を求める問題です。

考察

各生徒 \(i\) はプレゼントを渡す相手 \(T_i\) が決まっています。ここで重要な気づきは、プレゼントを1つでも受け取った生徒とは、\(T_1, T_2, \ldots, T_N\) の中に登場する出席番号のことであるという点です。

例えば \(N = 4\)、\(T = [2, 3, 2, 1]\) の場合を考えます。

• 生徒 1：生徒 4 からもらえる → 受け取れた ✅
• 生徒 2：生徒 1 と生徒 3 からもらえる → 受け取れた ✅
• 生徒 3：生徒 2 からもらえる → 受け取れた ✅
• 生徒 4：誰からももらえない → 受け取れなかった ❌

\(T\) に登場する出席番号の集合は \(\{1, 2, 3\}\) で、その要素数は \(3\) です。全体 \(4\) 人からこれを引いて、答えは \(4 - 3 = 1\) 人です。

つまり、\(T\) の中に現れる異なる値（重複を除いた値）の個数を数えれば、プレゼントを受け取れた生徒の人数が分かります。\(N\) からその人数を引けば、受け取れなかった生徒の人数が求まります。

素朴に「各生徒 \(j\) について、\(T\) の中に \(j\) が存在するかを線形探索する」方法では \(O(N^2)\) となり、\(N\) が最大 \(2 \times 10^5\) の場合 TLE になる可能性があります。

アルゴリズム

1. \(T_1, T_2, \ldots, T_N\) を読み込む。
2. \(T\) の要素を集合（set）に変換する。集合は重複を自動的に排除するため、集合の要素数がプレゼントを受け取れた生徒の人数になる。
3. \(N\) から集合の要素数を引いた値が答え。

\[\text{答え} = N - |\{T_1, T_2, \ldots, T_N\}|\]

計算量

• 時間計算量: \(O(N)\) — リストを集合に変換する操作は各要素につき平均 \(O(1)\) のハッシュ操作で、全体で \(O(N)\)。
• 空間計算量: \(O(N)\) — 集合の保持に最大 \(O(N)\) の空間が必要。

実装のポイント

• Python の set を使うことで、重複排除が1行で簡潔に書けます。set(T) とするだけで \(T\) に含まれる異なる値の集合が得られます。

• 各生徒が「誰にプレゼントをもらったか」を個別に管理する必要はなく、「渡し先として指名された出席番号の種類数」だけ分かれば十分です。

  ソースコード

N = int(input())
T = list(map(int, input().split()))
received = set(T)
print(N - len(received))

この解説は claude4.6opus-thinking によって生成されました。