概要

\(N\) 人の生徒と \(M\) 組の友達関係が与えられたとき、各生徒について「友達の番号の総和」を計算し、その中の最大値を求める問題です。

考察

この問題で求められている「人気度」は、各生徒に紐付いている友達の番号をすべて足し合わせたものです。

例えば、生徒 \(1\) の友達が生徒 \(2\) と生徒 \(3\) である場合、生徒 \(1\) の人気度は \(2 + 3 = 5\) となります。 このように、すべての生徒について個別に合計値を計算していく必要があります。

効率的な解法

生徒の数 \(N\) と友達関係の数 \(M\) は最大で \(2 \times 10^5\) と大きいため、二重ループを使って「全生徒に対して、全友達関係をチェックする」ような処理をすると、計算時間がかかりすぎて制限時間内に終わりません。

しかし、各友達関係 \((U_i, V_i)\) は「生徒 \(U_i\) の友達に \(V_i\) が加わり、生徒 \(V_i\) の友達に \(U_i\) が加わる」という \(2\) つの情報として捉えることができます。 したがって、与えられた \(M\) 個の友達関係を順番に \(1\) 回ずつ処理し、各生徒の合計値を更新していけば、効率よく答えを求めることができます。

アルゴリズム

1. 長さ \(N+1\) の配列 popularity を用意し、すべて \(0\) で初期化します。
   • インデックスを生徒の番号と一致させるため、サイズを \(N+1\) にしています。
2. 与えられた \(M\) 組の友達関係 \((U_i, V_i)\) を \(1\) つずつ取り出し、以下の処理を行います。
   • popularity[U_i] に \(V_i\) を加算する。
   • popularity[V_i] に \(U_i\) を加算する。
3. すべての友達関係を処理した後、popularity 配列の中の最大値を見つけて出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 配列の初期化に \(O(N)\)、\(M\) 個の入力を処理するのに \(O(M)\)、最後に最大値を探すのに \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 各生徒の人気度を保持するための配列 popularity のサイズが \(N\) に比例します。

実装のポイント

• 高速な入出力: Python で入力データが多い場合（今回のように \(M\) が \(2 \times 10^5\) 程度ある場合）、input() を繰り返すよりも sys.stdin.read().split() などを使って一括で読み込む方が実行時間を短縮できます。

• インデックスの管理: 生徒の番号が \(1\) から \(N\) までであるため、配列のサイズを \(N+1\) にしておくと、生徒番号をそのままインデックスとして扱えるので実装ミスを防げます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを取得し、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用してデータを効率的に取得します
    it = iter(input_data)
    
    # 生徒の人数 N と友達関係の数 M を取得
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # 各生徒の人気度を格納する配列を初期化（1番からN番まで）
    # インデックス 0 は使用しませんが、計算の簡略化のため N+1 のサイズを確保します
    popularity = [0] * (N + 1)
    
    # M 組の友達関係を処理
    for _ in range(M):
        try:
            u = int(next(it))
            v = int(next(it))
            # 生徒 u の人気度に友達 v の番号を加算
            popularity[u] += v
            # 生徒 v の人気度に友達 u の番号を加算
            popularity[v] += u
        except StopIteration:
            break
            
    # 全生徒の人気度の中から最大値を出力
    # popularity[0] は常に 0 であり、人気度は非負であるため max() の結果に影響しません
    print(max(popularity))

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。