概要

各ラウンドで、ある選手の得点が他の全選手の得点の最大値の2倍以上であるようなラウンドの数を求める問題です。

考察

重要な気づき：「ずば抜けている」のは最高得点の選手だけ

ある選手 \(i\) がラウンド \(j\) でずば抜けているとは、\(S_{j,i} \geq 2 \times M_{j,i}\)（\(M_{j,i}\) は選手 \(i\) 以外の最大得点）を満たすことです。

ここで、もし選手 \(i\) がそのラウンドで最高得点でなければ、\(M_{j,i} \geq S_{j,i}\) となるため、\(S_{j,i} \geq 2 \times M_{j,i}\) を満たすことは不可能です（得点は \(1\) 以上なので）。

つまり、ずば抜けている可能性があるのは、そのラウンドの最高得点者だけです。

最高得点者にとっての \(M_{j,i}\) は？

最高得点者にとっての「自分以外の全選手の得点の最大値」は、そのラウンドの 2番目に大きい得点 に等しくなります。

したがって、各ラウンドについて 1位の得点と2位の得点 さえ分かれば判定できます。

具体例

例えばあるラウンドの得点が \([30, 10, 15, 5]\) だったとします。 - 1位の得点: \(30\)、2位の得点: \(15\) - \(30 \geq 2 \times 15 = 30\) → 条件を満たすので「ずば抜けている」

得点が \([20, 10, 15, 5]\) だった場合： - 1位の得点: \(20\)、2位の得点: \(15\) - \(20 \geq 2 \times 15 = 30\) → 満たさないので「ずば抜けていない」

アルゴリズム

1. 各ラウンドについて、\(N\) 人の得点を読み込む。
2. 1回のスキャンで 最大値（max1） と 2番目に大きい値（max2） を求める。
   • 現在の値が max1 以上なら、max2 を旧 max1 に更新し、max1 を現在の値に更新。
   • そうでなく max2 より大きければ、max2 を更新。
3. \(\text{max1} \geq 2 \times \text{max2}\) が成り立てば、そのラウンドには「ずば抜けた選手」が存在する。
4. 条件を満たすラウンド数をカウントして出力する。

全選手の得点をソートする方法（\(O(N \log N)\)）でも解けますが、上位2つだけを求めればよいので \(O(N)\) で十分です。

計算量

• 時間計算量: \(O(N \times T)\)
  • 各ラウンドで \(N\) 人の得点を1回走査するだけなので、全体で \(O(N \times T)\) です。制約より \(N \times T \leq 10^6\) なので十分高速です。
• 空間計算量: \(O(N)\)
  • 各ラウンドの得点を一時的に保持するだけで済みます。

実装のポイント

• 高速な入力: Python では sys.stdin.buffer.read() で一括読み込みし、split() で分割する方法が高速です。\(N \times T\) が最大 \(10^6\) になるため、通常の input() を繰り返すと遅くなる可能性があります。

• 上位2つの値の求め方: max1 と max2 を初期値 \(0\) で管理し、各要素と比較して更新します。得点が \(1\) 以上であることが保証されているので、初期値 \(0\) で問題ありません。

• 同点の扱い: 最高得点の選手が複数いる場合、max1 と max2 が同じ値になります。このとき \(\text{max1} \geq 2 \times \text{max2}\) は成り立たないので、正しく「ずば抜けていない」と判定されます（1つのラウンドでずば抜けている選手は高々1人という条件とも整合します）。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    count = 0
    for _ in range(T):
        scores = input_data[idx:idx+N]
        idx += N
        
        # Find the top two values
        max1 = 0
        max2 = 0
        for k in range(N):
            v = int(scores[k])
            if v >= max1:
                max2 = max1
                max1 = v
            elif v > max2:
                max2 = v
        
        # The best player's score is max1, the second best is max2
        # For the best player, M = max2
        # They are "outstanding" if max1 >= 2 * max2
        if max1 >= 2 * max2:
            count += 1
    
    print(count)

main()

---

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