概要

各ラウンドごとに「最高得点の選手が、他の全員の最高得点の \(2\) 倍以上か」を判定し、そのようなラウンド数を数える問題です。

考察

ラウンド \(j\) で選手 \(i\) がずば抜けている条件は
\(S_{j,i} \ge 2 \times M_{j,i}\)（\(M_{j,i}\) は「選手 \(i\) 以外」の最大得点）です。

ここで重要な観察は次の2点です。

1. ずば抜けている選手がいるなら、その人はそのラウンドの単独1位である
   もし最高得点が同点で複数人いると、ある選手を除いた最大値 \(M_{j,i}\) も同じ最高点になってしまい、
   \(S_{j,i} \ge 2 \times M_{j,i}\) は（\(S_{j,i} \ge 2S_{j,i}\) となり）成立しません。
   よって「最高得点が一意（単独）」であることが必要です。

2. 「他の全員の最大値」は、最高得点が単独なら“2番目に大きい値”でよい
   最高得点を \(max1\)、2番目を \(max2\) とすると、最高得点が単独のとき
   \(M_{j,i} = max2\) になります。したがって判定は

   • 最高得点が単独（出現回数が1回）
   • \(max1 \ge 2 \times max2\)
     の2条件で十分です。

素朴に「各選手 \(i\) について \(M_{j,i}\) を求める」と、ラウンドごとに \(O(N^2)\) の計算になり得て間に合いません。
しかし、各ラウンドで 最大値と2番目の最大値だけ を取れば \(O(N)\) で判定できます。

例：得点が [10, 3, 4, 2] のとき
\(max1=10, max2=4\) なので、単独1位かつ \(10 \ge 2\times 4=8\) で「ずば抜けラウンド」です。
一方 [10, 5, 4] は \(max1=10, max2=5\) で \(10 \ge 10\) は成立するのでOK。
[10, 10, 1] は最高得点が2人いて単独でないためNGです。

アルゴリズム

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

1. そのラウンドの得点を左から読みながら、
   • 最大値 \(max1\)
   • 2番目の最大値 \(max2\)
   • 最大値の出現回数 \(cnt1\) を更新する。
2. ラウンドの読み取り後、
   • \(cnt1 == 1\)（最大値が単独）
   • \(max1 \ge 2 \times max2\) を満たせば答えを \(+1\)。

更新方法（1要素 \(x\) を読むたび）： - \(x > max1\)：\(max2 \leftarrow max1\), \(max1 \leftarrow x\), \(cnt1 \leftarrow 1\) - \(x == max1\)：\(cnt1 \leftarrow cnt1 + 1\) - \(max2 < x < max1\)：\(max2 \leftarrow x\)

これで各ラウンドを1回走査するだけで判定できます。

計算量

• 時間計算量: \(O(NT)\)（全入力を1回なめるだけ。制約 \(NT \le 10^6\) なので十分高速）
• 空間計算量: \(O(1)\)（各ラウンドで最大・2番目・回数など定数個のみ保持）

実装のポイント

• 最大値が単独かどうかが重要なので、最大値の出現回数 \(cnt1\) を必ず数えます。

• 入力サイズが最大で \(10^6\) 個の整数と大きいため、Pythonでは sys.stdin.buffer.read() による高速入力を使うと安定します（提示コードはバイト列から整数を手動でパース）。

• \(max2\) の初期値は \(-1\) など十分小さい値でよいです（得点は \(1\) 以上なので問題ありません）。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read()
    n = len(data)
    idx = 0

    def read_int():
        nonlocal idx
        while idx < n and data[idx] <= 32:
            idx += 1
        val = 0
        while idx < n and data[idx] > 32:
            val = val * 10 + (data[idx] - 48)
            idx += 1
        return val

    N = read_int()
    T = read_int()

    ans = 0
    for _ in range(T):
        max1 = -1
        max2 = -1
        cnt1 = 0
        for _ in range(N):
            x = read_int()
            if x > max1:
                max2 = max1
                max1 = x
                cnt1 = 1
            elif x == max1:
                cnt1 += 1
            elif x > max2:
                max2 = x
        if cnt1 == 1 and max1 >= 2 * max2:
            ans += 1

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。