概要

各ラウンドにおいて、最高得点者のスコアが2番目に高いスコアの2倍以上であるようなラウンドがいくつあるかを数える問題です。

考察

問題文の「ある選手が他の全選手の得点の最大値の2倍以上である」という条件を満たす可能性があるのは、当然ながらそのラウンドで最高得点を取った選手のみです。

したがって、すべての選手について「自分以外の最大値」を毎回探すような素朴な方法（1ラウンドあたり \(O(N^2)\) の計算量）をとると、全体で \(O(T N^2)\) となり、制約（\(N \times T \le 10^6\)）の下では実行時間制限（TLE）に引っかかってしまいます。

これを解決するための重要な気づきは、「各ラウンドにおいて、1番大きい得点と2番目に大きい得点だけ分かればよい」ということです。 1番大きい得点を \(m_1\)、2番目に大きい得点を \(m_2\) としたとき、\(m_1 \ge 2 \times m_2\) が成り立てば、そのラウンドには「ずば抜けている」選手が存在することになります。

具体例で考えてみましょう： - 得点が [10, 3, 4] の場合：1番目は \(10\)、2番目は \(4\) です。\(10 \ge 2 \times 4\) が成り立つため、条件を満たします。 - 得点が [10, 6, 10] の場合：1番目は \(10\)、2番目も \(10\) です。\(10 \ge 2 \times 10\) は成り立たないため、条件を満たしません。

アルゴリズム

各ラウンドについて、以下の手順を行います。

1. そのラウンドの全選手の得点リストを受け取る。
2. リストの中から最大値 \(m_1\) を見つける。
3. リストから \(m_1\) を1つだけ取り除く。
4. 残ったリストの中から再び最大値を見つける。これが元のリストにおける2番目に大きい値 \(m_2\) となる。
5. \(m_1 \ge 2 \times m_2\) が成り立つか判定し、成り立てば答えのカウントを \(1\) 増やす。
6. すべてのラウンドについて上記を繰り返し、最終的なカウントを出力する。

計算量

• 時間計算量: \(O(N \times T)\) 各ラウンドにおいて、最大値の取得 max() と要素の削除 remove() はいずれも \(O(N)\) の操作です。これを \(T\) ラウンド繰り返すため、全体の計算量は \(O(N \times T)\) となります。制約の \(N \times T \le 10^6\) に対して十分高速に動作します。
• 空間計算量: \(O(N \times T)\) 入力を sys.stdin.read().split() で一括して読み込んでリストに保持しているため、入力データ全体を保持する \(O(N \times T)\) のメモリを使用します。

実装のポイント

• 入力の高速化: Pythonでは入力データが多い場合、input() を何度も呼ぶと遅延が発生することがあります。今回のように sys.stdin.read().split() を使って入力を一括で読み込むことで、I/O（入出力）のオーバーヘッドを大幅に削減できます。

• remove() メソッドの性質: scores.remove(m1) は、リストの中から最初に見つかった m1 を 1つだけ 削除します。そのため、もし最高得点が同点で複数人いた場合（例：[10, 6, 10]）でも、1つ目の 10 だけが消え、2番目の最大値 \(m_2\) として正しくもう一つの 10 を取得することができます。

• 別解（ソート）: 得点リストを降順にソート（scores.sort(reverse=True)）して、m1 = scores[0], m2 = scores[1] と取得する方法もあります。この場合の1ラウンドあたりの計算量は \(O(N \log N)\) となりますが、今回の制約であればソートを用いても十分に間に合います。ただし、最大値を2回探す今回のアプローチ \(O(N)\) の方がより高速です。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    N = int(data[0])
    T = int(data[1])
    
    ans = 0
    idx = 2
    for _ in range(T):
        scores = [int(x) for x in data[idx:idx+N]]
        idx += N
        
        m1 = max(scores)
        scores.remove(m1)
        m2 = max(scores)
        
        if m1 >= m2 * 2:
            ans += 1
            
    print(ans)

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。