概要

各選手の最終得点を計算ルールに従って求め、基準点未満の選手（予選落ち）の人数を数える問題です。

考察

この問題では、審査員の人数 \(M\) によって最終得点の計算方法が変わります。

採点ルールの理解

• \(M \geq 3\) の場合：最高点と最低点を1つずつ除外してから平均を計算します。これは実際のフィギュアスケートでも使われる方式で、極端な採点（ひいき/過小評価）の影響を減らす目的があります。
• \(M \leq 2\) の場合：除外すると得点が残らないか1つしか残らないため、全ての得点をそのまま平均します。

具体例

例えば、ある選手が5人の審査員から \([60, 70, 80, 90, 100]\) という得点を受けた場合： - 最高点 \(100\) と最低点 \(60\) を除外 - 残りは \([70, 80, 90]\) - 平均は \((70 + 80 + 90) / 3 = 80\) 点

素朴なアプローチで問題ない理由

この問題では \(N \leq 10^5\)、\(M \leq 100\) という制約があり、各選手について \(O(M \log M)\) の処理（ソート）を行っても十分高速です。特別な工夫は不要で、問題文の通りに素直に実装すれば良いです。

アルゴリズム

1. 各選手について、\(M\) 個の得点を読み込む
2. \(M \geq 3\) の場合：
   • 得点をソートする
   • 最小値（先頭）と最大値（末尾）を除いた部分を取り出す
   • その平均を計算（小数点以下切り捨て）
3. \(M \leq 2\) の場合：
   • 全得点の平均を計算（小数点以下切り捨て）
4. 最終得点が基準点 \(K\) 未満なら、予選落ちカウンターを増やす
5. 全選手を処理したら、予選落ち人数を出力

ソートを使う理由

ソートすると配列は昇順に並ぶため、scores_sorted[0] が最小値、scores_sorted[-1] が最大値になります。Pythonのスライス scores_sorted[1:-1] を使えば、最小と最大を除いた部分を簡単に取り出せます。

計算量

• 時間計算量: \(O(N \cdot M \log M)\)
  • 各選手について得点のソートに \(O(M \log M)\)
  • \(N\) 人分繰り返すので全体で \(O(N \cdot M \log M)\)
• 空間計算量: \(O(M)\)
  • 各選手の得点を一時的に保持するのに \(O(M)\)

実装のポイント

• 小数点以下切り捨て：Pythonでは整数同士の除算に // 演算子を使うことで、自動的に切り捨てが行われます。

• スライスの活用：scores_sorted[1:-1] で先頭と末尾を除いた部分配列を取得できます。これは「最高点と最低点を除く」処理を簡潔に書く方法です。

• 条件分岐：\(M \geq 3\) と \(M \leq 2\) で処理を分けることを忘れないようにしましょう。\(M = 1\) や \(M = 2\) のケースでも正しく動作することを確認しましょう。

  ソースコード

def solve():
    N, M, K = map(int, input().split())
    
    eliminated = 0
    
    for _ in range(N):
        scores = list(map(int, input().split()))
        
        if M >= 3:
            # 最高点と最低点を1つずつ除いた残りの平均
            scores_sorted = sorted(scores)
            remaining = scores_sorted[1:-1]  # 最小と最大を除く
            final_score = sum(remaining) // len(remaining)
        else:
            # M <= 2 の場合：すべての得点の平均
            final_score = sum(scores) // len(scores)
        
        if final_score < K:
            eliminated += 1
    
    print(eliminated)

solve()

---

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