概要

\(N\) 人の選手がそれぞれ \(M\) 人の審査員から点数を付けられ、各選手について最高点と最低点を除いた残りの点数の合計が最終スコアとなる。最終スコアが最も高い選手の番号を求めよ。

考察

この問題では、各選手について以下のような処理を行う必要があります： 1. \(M\) 個の点数から最大値と最小値を1つずつ取り除く。 2. 残った \(M - 2\) 個の点数の合計を求める。

素朴な方法として、毎回ソートして先頭と末尾を除くことを考えると、時間計算量は \(O(M \log M)\) となり、全体では \(O(N \cdot M \log M)\) になります。制約より \(N \times M \leq 10^6\) なので、最悪ケースで \(M\) が大きいとTLEになる可能性があります。

しかし、実はソートせずに最大値・最小値を1つずつ引くだけで処理できます。つまり、全点数の合計から最大値と最小値を引けば、求めたい「残りの合計」が得られます。これにより、各選手に対して \(O(M)\) で処理でき、全体で \(O(N \cdot M)\) となります。

また、同点の場合には選手番号が最も小さい人を選ぶ必要があることに注意しましょう。この判定も適切に行うことで、正しい答えを得ることができます。

アルゴリズム

1. 各選手について、点数リストを受け取る。
2. そのリストの合計、最大値、最小値を計算する。
3. 最終スコア = 合計 - 最大値 - 最小値 を計算する。
4. これまでの最大スコアと比較し、より高ければ更新。同じ場合は選手番号が小さい方を選ぶ。
5. 全選手を確認した後、最もスコアが高い選手の番号を出力する。

例

例えば、選手1の点数が [90, 85, 95, 80] の場合： - 合計: \(90 + 85 + 95 + 80 = 350\) - 最大値: \(95\) - 最小値: \(80\) - 最終スコア: \(350 - 95 - 80 = 175\)

計算量

• 時間計算量: \(O(N \cdot M)\)
• 空間計算量: \(O(N \cdot M)\) （入力を保持する配列による）

実装のポイント

• 入力が多いので高速化のために sys.stdin.read を使用している。
• 各選手の点数を一度に読み込み、リストとして管理することで効率よく処理できる。
• 最終スコアの比較時に、同点時の選手番号の扱いに注意すること。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    scores = []
    index = 2
    for i in range(N):
        player_scores = list(map(int, data[index:index+M]))
        index += M
        scores.append(player_scores)
    
    max_score = -1
    winner = -1
    
    for i in range(N):
        s_list = scores[i]
        total = sum(s_list)
        max_s = max(s_list)
        min_s = min(s_list)
        final_score = total - max_s - min_s
        
        if final_score > max_score:
            max_score = final_score
            winner = i + 1
        elif final_score == max_score and (winner == -1 or i + 1 < winner):
            winner = i + 1
            
    print(winner)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。