概要

各選手について「得点の合計・最小値・最大値」から最終得点（平均の切り捨て）を計算し、基準点 \(K\) 未満の人数を数える問題です。

考察

重要なのは、最終得点の計算方法が \(M \ge 3\) と \(M \le 2\) で分かれる点です。

• \(M \ge 3\) のとき：最高点と最低点を 1 つずつ除外して平均を取る
  つまり、得点の配列を \(a_1,\dots,a_M\) とすると
  [ \text{score}=\left\lfloor\frac{\sum a_i - \min(a) - \max(a)}{M-2}\right\rfloor ]
• \(M \le 2\) のとき：全ての平均
  [ \text{score}=\left\lfloor\frac{\sum a_i}{M}\right\rfloor ]

素朴に「毎回得点をソートして最小・最大を除く」でも正しくは求まりますが、各選手ごとに \(O(M \log M)\) かかります。\(N\) が最大 \(10^5\) なので、合計で \(10^5\) 回ソートすることになり、Python では入力も含めて重くなりがちです。

そこで、ソートをせずに 1 回の走査で合計・最小・最大を求める と、各選手を \(O(M)\) で処理できます。

例：\(M=5\)、得点が \([10, 7, 9, 3, 8]\) のとき
- 合計 \(s=37\)、最小 \(mn=3\)、最大 \(mx=10\)
- 除外後の合計は \(37-3-10=24\)、残りは \(5-2=3\) 個
- 最終得点は \(\left\lfloor 24/3 \right\rfloor = 8\)

アルゴリズム

1. 入力 \(N, M, K\) を読む。
2. 予選落ち人数 cnt=0 を用意する。
3. 各選手について以下を行う：
   • \(M \ge 3\) の場合
     
     • 得点を \(M\) 個読みながら、合計 s、最小 mn、最大 mx を更新する。
     • [ \text{score} = (s - mn - mx) // (M - 2) ]
     • score < K なら cnt += 1
   • \(M \le 2\) の場合
     
     • \(M\) 個の合計 s を取り、score = s // M
     • score < K なら cnt += 1
4. cnt を出力する。

計算量

• 時間計算量: \(O(NM)\)（各選手の \(M\) 個の得点を 1 回ずつ見るだけ）
• 空間計算量: \(O(1)\)（各選手について合計・最小・最大など定数個の変数のみ）

実装のポイント

• \(M \ge 3\) と \(M \le 2\) で処理を分ける：\(M-2=0\) を避けるためにも必須です。

• 平均の「小数点以下切り捨て」は、Python では 整数除算 // で表現できます。

• \(N\) が大きいので、Python では入力がボトルネックになりがちです。提出コードでは sys.stdin.buffer.read() と自前の整数パーサで高速化しています。

  ソースコード

import sys

data = sys.stdin.buffer.read()
n = len(data)
idx = 0

def next_int():
    global idx
    while idx < n and data[idx] <= 32:
        idx += 1
    val = 0
    while idx < n and data[idx] > 32:
        val = val * 10 + (data[idx] - 48)
        idx += 1
    return val

N = next_int()
M = next_int()
K = next_int()

cnt = 0
if M >= 3:
    denom = M - 2
    for _ in range(N):
        s = 0
        mn = 101
        mx = -1
        for _ in range(M):
            x = next_int()
            s += x
            if x < mn:
                mn = x
            if x > mx:
                mx = x
        score = (s - mn - mx) // denom
        if score < K:
            cnt += 1
else:
    for _ in range(N):
        s = 0
        for _ in range(M):
            s += next_int()
        score = s // M
        if score < K:
            cnt += 1

sys.stdout.write(str(cnt))

この解説は gpt-5.2-high によって生成されました。