概要

各ラウンドにおいて、ある選手の得点が他の全選手の最高得点の2倍以上であるかどうかを判定し、そのようなラウンドの数を数える問題です。

考察

問題の定義から、各ラウンドでずば抜けている選手が存在するかどうかを判定するには、以下の2つの情報が必要です： 1. そのラウンドの最高得点 2. 最高得点を持つ選手を除いた中の最高得点（2番目の得点）

なぜなら、ずば抜けているかどうかの条件は「最高得点 ≥ 2 × (2番目の得点)」だからです。各ラウンドのデータサイズは選手数Nで、N×T ≤ 10^6という制約があるため、各ラウンドごとに線形探索で最高得点と2番目の得点を求めれば十分効率的です。

アルゴリズム

1. 各ラウンドについて、得点のリストを受け取る
2. そのラウンドの最高得点（max1）と2番目の得点（max2）を求める
   • 最高得点を更新するときは、元の最高得点を2番目の得点に移す
   • 最高得点以下だが2番目の得点より大きいときは2番目の得点を更新する
3. 条件「max1 ≥ 2 × max2」を満たすかチェックする
   • 満たす場合は、そのラウンドでずば抜けた選手が存在するのでカウントを増やす
4. 全ラウンドについて処理した後、カウントを出力する

計算量

• 時間計算量: \(O(N \times T)\)
  • 各ラウンドで\(O(N)\)の処理を行うため、全体で\(O(N \times T)\)
  • 制約\(N \times T \leq 10^6\)より十分高速
• 空間計算量: \(O(N \times T)\)
  • 入力データを保持するための空間（ただし、問題の制約上\(10^6\)要素まで）

実装のポイント

• 各ラウンドの処理では、最高得点と2番目の得点を同時に追跡する

• 2番目の得点が存在しない場合（全選手が同じ得点の場合）のために、max2の初期値を-1とし、条件判定時に0として扱う

• 入力データを一括で読み込むことで効率化を図っている

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    t = int(data[1])
    index = 2
    count = 0
    
    for _ in range(t):
        round_scores = list(map(int, data[index:index+n]))
        index += n
        
        max1 = -1
        max2 = -1
        max_index = -1
        
        for i, score in enumerate(round_scores):
            if score > max1:
                max2 = max1
                max1 = score
                max_index = i
            elif score > max2:
                max2 = score
        
        if max2 == -1:
            max2 = 0
        
        if max1 >= 2 * max2:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

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