概要

各生徒がプレゼントを渡す相手の情報から、プレゼントを1つも受け取れなかった生徒の人数を求める問題です。

考察

この問題は、各生徒が誰にプレゼントを渡すかという情報（有向グラフの辺）が与えられています。重要な観察点は、プレゼントを受け取る生徒は少なくとも1人からプレゼントが届くということです。つまり、各生徒がプレゼントを受け取ったかどうかは、その生徒が誰かから指名されているかどうかで判定できます。

具体的には、生徒 \(i\) がプレゼントを受け取るためには、少なくとも1人の生徒が \(T_j = i\) となるような \(j\) が存在する必要があります。逆に、どの生徒からも指名されていない生徒は、プレゼントを1つも受け取れないことになります。

素朴なアプローチとして、各生徒について全員の指名先を調べてチェックする方法が考えられますが、これでは \(O(N^2)\) の時間計算量となり、制約 \(N \leq 2 \times 10^5\) では実行時間が間に合いません。

アルゴリズム

効率的な解法として、以下の手順を考えます： 1. サイズ \(N+1\) のブーリアン配列 received を用意し、すべて False で初期化します 2. 各生徒 \(i\) の指名先 \(T_i\) を見て、received[T_i] を True に設定します - これにより、生徒 \(T_i\) は少なくとも1つのプレゼントを受け取ることが分かります 3. 最後に、received 配列を生徒番号1からNまで調べて、False となっている生徒の数を数えます - これらの生徒は誰からも指名されていないため、プレゼントを受け取れません

このアルゴリズムは、入力配列を2回走査するだけの単純なものですが、効率的に問題を解くことができます。

計算量

• 時間計算量: \(O(N)\)
  • 入力の読み込みと配列の初期化が \(O(N)\)
  • 指名先の処理が \(O(N)\)
  • 結果のカウントが \(O(N)\)
• 空間計算量: \(O(N)\)
  • received 配列のための \(O(N)\) のメモリを使用

実装のポイント

1. 配列のインデックスは1-indexedなので、サイズ \(N+1\) の配列を用意し、インデックス0は使用しないようにします

2. 入力の読み込みでは、sys.stdin.read() を使って一度にすべてのデータを読み込むことで、高速な処理を実現しています

3. ブーリアン配列の初期化は [False] * (N+1) で行い、メモリ効率と速度を最適化しています

4. 最終的には received 配列の False の数を数えるだけで答えが得られます

   ソースコード

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    T = list(map(int, data[1:]))
    
    received = [False] * (N + 1)
    for t in T:
        received[t] = True
    
    count = 0
    for i in range(1, N + 1):
        if not received[i]:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。