概要

\(N\) 人の選手が \(M\) 人の審査員から点数を受け取ります。各選手の「最高点と最低点を除いた \(M-2\) 個の合計点」を計算し、その値が最も高い選手の番号（同点なら番号が最小の選手）を求める問題です。

考察

各選手の最終スコアを計算するために、以下の手順を考えます。 1. \(M\) 個の点数の合計値を求める。 2. \(M\) 個の点数の中から最高点と最低点を見つける。 3. 合計値から最高点と最低点を 1 つずつ引く。

例えば、ある選手の点数が \([10, 20, 30, 40, 50]\) だった場合、合計は \(150\)、最高点は \(50\)、最低点は \(10\) です。最終スコアは \(150 - 50 - 10 = 90\) となります。

注意すべき点： - 同点の場合の処理: 最終スコアが同じ選手が複数いる場合、番号が最も小さい選手を出力する必要があります。選手を \(1\) 番から順番に処理し、これまでの最大スコアを「厳密に上回ったときだけ」記録を更新するようにすれば、自然と番号が小さい選手が優先されます。 - 制約と効率: \(N \times M\) が最大で \(10^6\) と比較的大きいため、入力処理を効率的に行う必要があります。Pythonでは input() を何度も呼び出すよりも、一括で読み込むなどの工夫が有効です。

アルゴリズム

1. 現在の最大スコア max_final_score を \(-1\)、その選手の番号 best_athlete_idx を \(-1\) で初期化します。
2. 選手 \(i = 1, 2, \dots, N\) について以下を繰り返します：
   • 選手 \(i\) の \(M\) 個の点数を読み込む。
   • その合計 \(S\)、最大値 \(Max\)、最小値 \(Min\) を求める。
   • 最終スコア \(Score = S - Max - Min\) を計算する。
   • もし \(Score > max_final_score\) ならば：
     • max_final_score を \(Score\) で更新する。
     • best_athlete_idx を \(i\) で更新する。
3. 最終的に保持されている best_athlete_idx を出力します。

計算量

• 時間計算量: \(O(NM)\)
  • 全ての選手の全ての点数（合計 \(N \times M\) 個）を一度ずつ走査するため、入力のサイズに比例した時間で計算が終わります。
• 空間計算量: \(O(NM)\)
  • sys.stdin.read().split() を使用して入力を一括でリストに格納する場合、入力全データをメモリに保持するため \(O(NM)\) となります。

実装のポイント

• 効率的な入力: sys.stdin.read().split() と iter() を組み合わせることで、大量の数値を高速に読み込み、一つずつ取り出すことができます。

• islice の活用: itertools.islice を使うと、イテレータから特定の個数（今回は \(M\) 個）だけ要素を効率よく切り出してリスト化できます。

• 更新条件: if final_score > max_final_score: と比較演算子に > を使うことで、スコアが同じ場合には更新が走らず、先に登場した（＝番号が小さい）選手が保持されるようになっています。

  ソースコード

import sys
from itertools import islice

def main():
    # 入力をすべて読み込み、空白区切りでトークンに分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用してトークンを順次処理する
    it = iter(input_data)
    try:
        n = int(next(it))
        m = int(next(it))
    except StopIteration:
        return
    
    max_final_score = -1
    best_athlete_idx = -1
    
    # 各選手についてスコアを計算する
    for i in range(1, n + 1):
        # 審査員 m 人分のスコアを整数リストとして取得する
        # islice を使うことで、イテレータから必要な分だけ効率的に取り出す
        scores = list(map(int, islice(it, m)))
        
        if not scores:
            break
            
        # 最終スコアの計算: 合計から最高点と最低点を1つずつ引く
        current_sum = sum(scores)
        current_max = max(scores)
        current_min = min(scores)
        final_score = current_sum - current_max - current_min
        
        # 最高スコアを更新した場合、選手の番号を記録する
        # 同じスコアの場合は、番号が小さい方を優先するため、より大きい場合のみ更新する
        if final_score > max_final_score:
            max_final_score = final_score
            best_athlete_idx = i
            
    # 結果を出力する
    if best_athlete_idx != -1:
        print(best_athlete_idx)

if __name__ == '__main__':
    main()

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