概要

各選手について「合計点から最大点と最小点を1つずつ引いた値」を最終スコアとして計算し、最終スコアが最大（同点なら番号が最小）の選手番号を求めます。

考察

最終スコアは「最高点・最低点を除外した残りの合計」ですが、これをそのまま実装しようとして毎回点数をソートすると、1人あたり \(O(M \log M)\) かかり、全体で \(O(NM \log M)\) となって無駄が大きくなります。

ここで重要な気づきは、除外するのは 最大値1つと最小値1つだけ なので、並べ替えは不要だということです。

各選手の点数列 \(S_{i,1},\dots,S_{i,M}\) について、 - 合計 \(s=\sum_j S_{i,j}\) - 最小値 \(mn=\min_j S_{i,j}\) - 最大値 \(mx=\max_j S_{i,j}\)

を1回の走査で求めれば、最終スコアは $\( score = s - mn - mx \)$ で一発で計算できます。

また、同点のときは番号が小さい方を選ぶ必要がありますが、更新条件を「\(score\) が 厳密に 大きいときだけ更新」にすれば、最初に出てきた最大スコアの選手（=番号が最小）が残ります。

（例）点数が [10, 3, 7, 8] のとき、合計 \(28\)、最小 \(3\)、最大 \(10\) なので最終スコアは \(28-3-10=15\) です。

アルゴリズム

1. 変数 best_score（これまでの最大最終スコア）と best_idx（その選手番号）を用意する。
2. 各選手 \(i=1..N\) について：
   1. s=0, mn=101, mx=0 を初期化する（点数は \(1..100\) なのでこの初期値で安全）。
   2. \(M\) 個の点数を読みながら、s に加算しつつ mn と mx を更新する。
   3. score = s - mn - mx を計算する。
   4. score > best_score なら best_score=score, best_idx=i に更新する（同点は更新しない）。
3. best_idx を出力する。

計算量

• 時間計算量: \(O(NM)\)（各点数を1回ずつ見るだけ）
• 空間計算量: \(O(1)\)（各選手について合計・最小・最大のみ保持。入力全体を配列に持たない）

実装のポイント

• ソートしない：必要なのは合計・最小・最大だけなので、1回の走査で十分です。

• 同点処理：更新条件を > のみにすることで、同点なら先に出た（番号が小さい）選手が選ばれます。

• 高速入力：制約で \(N \times M \le 10^6\) と大きめなので、Pythonでは sys.stdin.buffer.read() を使った整数パーサ（提示コードの int_reader）で高速に読み取ると安定します。

  ソースコード

import sys

def int_reader():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield num

it = int_reader()
N = next(it)
M = next(it)

best_score = -10**18
best_idx = 1

for idx in range(1, N + 1):
    s = 0
    mn = 101
    mx = 0
    for _ in range(M):
        x = next(it)
        s += x
        if x < mn:
            mn = x
        if x > mx:
            mx = x
    score = s - mn - mx
    if score > best_score:
        best_score = score
        best_idx = idx

sys.stdout.write(str(best_idx))

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