概要

\(N\) 人の選手がそれぞれ \(M\) 人の審査員から受けた点数について、最高点と最低点を1つずつ除いた合計（最終スコア）を計算し、最終スコアが最も高い選手の番号を求める問題です。

考察

重要な気づき

各選手の最終スコアは「全審査員の点数の合計 − 最高点 − 最低点」で求められます。つまり、わざわざ配列をソートして最高点・最低点を除外する必要はなく、合計・最小値・最大値の3つを求めるだけで十分です。

具体例

例えば、ある選手が5人の審査員から [8, 6, 9, 7, 10] という点数を受けた場合： - 合計: \(8 + 6 + 9 + 7 + 10 = 40\) - 最低点: \(6\)、最高点: \(10\) - 最終スコア: \(40 - 6 - 10 = 24\)

素朴なアプローチとの比較

素朴に各選手の点数をソートして最高点・最低点を除外する方法では、ソートに \(O(M \log M)\) かかります。一方、合計・最小値・最大値を1回の走査で求めれば \(O(M)\) で済みます。本問では \(N \times M \leq 10^6\) なのでソートでも間に合いますが、走査のみの方が定数倍が軽く確実です。

入力の高速化

\(N \times M\) が最大 \(10^6\) と大きいため、Pythonでは sys.stdin.buffer.read() で入力を一括読み込みすることで、1行ずつ input() を呼ぶよりも大幅に高速化できます。

アルゴリズム

1. \(N\) と \(M\) を読み込む。
2. 各選手 \(i\)（\(1 \leq i \leq N\)）について：
   • \(M\) 個の点数を読み込みながら、合計・最小値・最大値 を1回の走査で求める。
   • 最終スコアを \(\text{合計} - \text{最小値} - \text{最大値}\) として計算する。
3. 最終スコアが最大の選手の番号を記録する。同点の場合は番号が小さい方を優先する（先に見つかった方を保持すればよい）。
4. 結果を出力する。

計算量

• 時間計算量: \(O(N \times M)\)
  • 各選手について \(M\) 個の点数を1回走査するため。
• 空間計算量: \(O(N \times M)\)
  • 入力を一括読み込みするための領域。各選手の処理自体は \(O(M)\) のスライスで済む。

実装のポイント

• 入力の一括読み込み: sys.stdin.buffer.read().split() で全入力をバイト列として一括読み込みし、トークンに分割します。これによりPythonでも高速に入力を処理できます。

• 最小値・最大値の初期化: 点数は \(1\) 以上 \(100\) 以下なので、最小値の初期値を \(101\)、最大値の初期値を \(0\) にすることで、最初の要素で必ず更新されるようにしています。

• 同点時の処理: final_score > best_score と厳密な不等号で比較しているため、同スコアの場合は先に登場した（番号が小さい）選手が保持されます。特別な処理は不要です。

• int 変換の遅延: スライスした各要素を int(s) で変換しながら合計・最小・最大を同時に更新することで、無駄なリスト生成を避けています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    best_score = -1
    best_player = 1
    
    for i in range(1, N + 1):
        scores = input_data[idx:idx + M]
        idx += M
        total = 0
        mn = 101
        mx = 0
        for s in scores:
            v = int(s)
            total += v
            if v < mn:
                mn = v
            if v > mx:
                mx = v
        final_score = total - mn - mx
        if final_score > best_score:
            best_score = final_score
            best_player = i
    
    print(best_player)

main()

この解説は claude4.6opus-thinking によって生成されました。