概要

各選手の最終スコアを、審査員の点数から最高点と最低点を除いた合計で計算し、最もスコアが高い選手（同点なら番号が小さい方）を求める問題です。

考察

問題の要求を素直に実装する場合、各選手について以下の処理が必要です： 1. 審査員の点数から最高点と最低点を見つける 2. それらを除外して残りの点数の合計を計算する

しかし、点数が最大100と小さいことと、入力サイズが \(N \times M \leq 10^6\) であることから、各選手の点数リストをソートしても十分効率的です。ソートすることで、最小値と最大値が両端に配置され、簡単に除外できます。

アルゴリズム

1. 各選手 \(i\) (\(1 \leq i \leq N\)) について：
   • \(M\) 個の点数を受け取る
   • 点数リストを昇順にソートする
   • ソート後のリストの先頭（最小値）と末尾（最大値）を除いた部分の合計を計算する
2. 全選手の最終スコアを比較し、最大スコアを持つ選手を記録する（同点の場合は番号が小さい方を優先）

計算量

• 時間計算量: \(O(N \times M \log M)\)
  • 各選手の点数リストのソートに \(O(M \log M)\) かかり、これが \(N\) 回行われる
  • ただし \(N \times M \leq 10^6\) という制約から、最悪ケースでも \(10^6 \log 10^6 \approx 2 \times 10^7\) 程度で十分高速
• 空間計算量: \(O(N \times M)\)
  • 入力データを格納するためのメモリ

実装のポイント

• 入力データを一度に読み込むことで効率化

• ソート後のリストは scores[1:-1] で簡単に最小値と最大値を除外できる

• 同点の場合の処理を忘れずに実装（現在の最高スコア保持者より番号が小さい場合のみ更新）

• 選手番号は1-indexedである点に注意（コード中では0-indexedで処理しているため+1する）

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    index = 2
    
    max_score = -1
    best_player = -1
    
    for player in range(n):
        scores = list(map(int, data[index:index+m]))
        index += m
        
        scores.sort()
        total = sum(scores[1:-1])
        
        if total > max_score:
            max_score = total
            best_player = player + 1
        elif total == max_score:
            if player + 1 < best_player:
                best_player = player + 1
                
    print(best_player)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。