概要

\(N\) 人の選手が \(M\) 人の審査員から得点を受け取ります。審査員の人数 \(M\) に応じて決められたルール（最高点・最低点の除外など）で最終得点を計算し、その得点が基準点 \(K\) 未満となる「予選落ち」の人数を求める問題です。

考察

この問題のポイントは、条件分岐に従って正しく最終得点を計算すること、および \(N\) が大きいため効率的に処理すること の 2 点です。

1. 最終得点の計算ルール

   • \(M \geq 3\) のとき：合計点から「最大値 1 つ」と「最小値 1 つ」を引き、残りの \(M-2\) 個の平均（小数点以下切り捨て）を求めます。
   • \(M \leq 2\) のとき：単純に全 \(M\) 個の平均（小数点以下切り捨て）を求めます。 どちらの場合も「小数点以下切り捨て」を行うため、プログラミング言語の整数型同士の割り算（Python では // 演算子）がそのまま利用できます。

2. 制約と計算量

   • 選手の数 \(N\) は最大 \(10^5\)、審査員の数 \(M\) は最大 \(100\) です。
   • 全選手の得点を処理すると、読み込む数値の総数は最大 \(N \times M = 10^7\) 個になります。
   • 各選手に対して「合計・最大・最小」を求める操作は \(O(M)\) で行えるため、全体の計算量は \(O(N \times M)\) となります。これは一般的な制限時間（2秒程度）の中で十分に間に合う計算量です。

アルゴリズム

以下の手順で各選手の判定を行います。

1. 入力から \(N, M, K\) を受け取る。
2. 以下の処理を \(N\) 回繰り返す：
   • 選手 \(i\) の \(M\) 個の得点リスト \(S_i\) を読み込む。
   • \(M \geq 3\) の場合：
     • \(S_i\) の合計値を sum、最大値を max、最小値を min とする。
     • 最終得点 = (sum - max - min) // (M - 2)
   • \(M \leq 2\) の場合：
     • \(S_i\) の合計値を sum とする。
     • 最終得点 = sum // M
   • 最終得点が \(K\) 未満であれば、カウント用変数 fail_count を 1 増やす。
3. 最終的な fail_count を出力する。

計算量

• 時間計算量: \(O(N \times M)\)
  • 各選手について \(M\) 個の得点を 1 回ずつ走査するため、全体で \(N \times M\) 回の操作となります。
• 空間計算量: \(O(M)\)
  • 1 人分の得点リストを保持するために \(M\) のメモリを使用しますが、全選手のデータを同時に保持する必要はありません。

実装のポイント

• Python の // 演算子: 正の数同士の割り算において、a // b は a / b の結果の小数点以下を切り捨てた整数（床関数）を返します。問題文の「小数点以下切り捨て」の指示通りに動作します。

• 組み込み関数の活用: sum(), max(), min() は Python の内部で高速に処理されるため、自分でループを回して計算するよりも効率的です。

• 高速な入出力: \(N \times M\) が大きいため、input() よりも sys.stdin を使ってデータを読み込む方が実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # 標準入力から1行ずつ読み込むイテレータを作成
    input_iter = sys.stdin
    
    # 最初の行（N, M, K）を読み込む
    first_line = next(input_iter, None)
    if first_line is None:
        return
    
    params = first_line.split()
    if not params:
        return
        
    n = int(params[0])
    m = int(params[1])
    k = int(params[2])
    
    fail_count = 0
    
    # 審査員数 M が 3 以上の場合の処理
    if m >= 3:
        div = m - 2
        # 各選手の得点を処理
        for _ in range(n):
            line = next(input_iter, None)
            if line is None:
                break
            
            # 1行分の得点を整数のリストに変換
            scores = list(map(int, line.split()))
            if not scores:
                continue
            
            # 最高点と最低点を1つずつ除いた残りの得点の合計
            # sum, max, min は Python の組み込み関数で高速に動作する
            s_sum = sum(scores)
            s_max = max(scores)
            s_min = min(scores)
            
            # 最終得点の計算（小数点以下切り捨て）
            # Pythonの // 演算子は正の数に対して小数点以下を切り捨てる（床関数）
            final_score = (s_sum - s_max - s_min) // div
            
            # 基準点 K 未満であれば予選落ちとしてカウント
            if final_score < k:
                fail_count += 1
                
    # 審査員数 M が 2 以下の処理
    else:
        for _ in range(n):
            line = next(input_iter, None)
            if line is None:
                break
            
            scores = list(map(int, line.split()))
            if not scores:
                continue
            
            # すべての得点の平均値（小数点以下切り捨て）
            final_score = sum(scores) // m
            
            if final_score < k:
                fail_count += 1
                
    # 予選落ちの人数を出力
    sys.stdout.write(str(fail_count) + '\n')

if __name__ == '__main__':
    solve()

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