概要

各ラウンドで「他の誰よりも圧倒的に高い得点を取った選手」がいるかどうかを判定し、そのようなラウンドの数を答える問題。

考察

この問題では、各ラウンドごとに以下の条件を満たす選手がいるかを判定する必要があります：

自分の得点 \(S_{j,i}\) が、他のすべての選手の得点の最大値 \(M_{j,i}\) の2倍以上である。

つまり、自分以外の最高得点を \(M_{j,i}\) としたときに
$\( S_{j,i} \geq 2 \times M_{j,i} \)$
が成り立てば「ずば抜けている」と判断できます。

素朴なアプローチとその問題

素朴には、各ラウンドごとに以下のように処理できます： 1. 各選手の得点を見て、最大値 \(max\) を求める。 2. 最大値を取った選手が1人だけかを確認。 3. さらに、2番目に高い得点 \(second\_max\) を探す。 4. \(max \geq 2 \times second\_max\) なら、その選手は「ずば抜けている」。

この方法自体は正しいですが、実装によっては非効率になることがあります。例えば、毎回ソートして2番目の値を取り出すと、時間計算量が悪くなります（後述）。

また、最大値が複数ある場合（例：3人がともに100点）は、誰も「ずば抜けている」とは言えません。この点も見落とさないように注意が必要です。

改善策

最大値と2番目の最大値を1パスで求めることで、効率よく判定できます： - 最大値の出現回数を数える → 複数回出てきたら即終了 - それ以外の値の中で最も大きいものを記録 → これが2番目の最大値

これにより、各ラウンドに対して線形時間で判定が可能です。

アルゴリズム

1. 各ラウンドについて以下の処理を行う：
   • 得点リストから最大値 \(max\) を求める。
   • \(max\) の出現回数を数える。
   • もし出現回数が2以上なら、「ずば抜けている」選手はいないので次のラウンドへ。
   • そうでない場合、2番目に大きな得点 \(second\_max\) を探索。
   • \(max \geq 2 \times second\_max\) ならカウントアップ。
2. 全ラウンド分のカウントを出力。

計算量

• 時間計算量: \(O(N \times T)\)
  各ラウンドで全選手を走査するので、合計 \(T\) 回 × \(N\) 人 = \(O(NT)\)。
• 空間計算量: \(O(N \times T)\)
  全ての得点データをメモリに保持しているため。

実装のポイント

• sys.stdin.read を使って高速入力を行うことで、大きな入力にも耐えられる。

• 各ラウンドごとに最大値と2番目の最大値を効率良く取得する。

• 最大値が複数ある場合はすぐにスキップすることで無駄な処理を避ける。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    T = int(data[1])
    
    # Read all scores into a list of lists
    scores = []
    index = 2
    for _ in range(T):
        round_scores = list(map(int, data[index:index + N]))
        scores.append(round_scores)
        index += N

    count = 0

    for round_scores in scores:
        max_score = max(round_scores)
        # Count how many times the maximum score appears
        max_count = round_scores.count(max_score)
        
        # If the max score appears more than once, no one can be outstanding
        if max_count > 1:
            continue
        
        # Find the second highest score
        second_max_score = 0
        for score in round_scores:
            if score < max_score and score > second_max_score:
                second_max_score = score
        
        # Check if the max score is at least twice the second max
        if max_score >= 2 * second_max_score:
            count += 1

    print(count)

if __name__ == "__main__":
    main()

---

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