概要

列の前方にいる「高身長グループ（\(S_j \ge T\)）」の中に、自分より厳密に背が高い人（\(S_j > S_i\)）がいる生徒の人数を、先頭から一度見るだけで数えます。

考察

生徒 \(i\) が「見上げる生徒」になる条件は、「自分より前にいる高身長グループの生徒の身長の最大値」が \(S_i\) より大きいことです。
つまり、前方にいる高身長グループの最大身長を \(M_i\) とすると、生徒 \(i\) は

• \(M_i > S_i\)

なら見上げる生徒です。

ここで重要なのは、「必要なのは最大値だけ」という点です。前にいる高身長グループの全員と比較する必要はありません。

素朴な方法が遅い理由

各 \(i\) について、\(1 \le j < i\) を全探索して条件を満たすか調べると、最悪で \(O(N^2)\) になります。
\(N \le 10^6\) なので、これは現実的に間に合いません。

どう解決するか

列を前から順に見ていき、「ここまでに見た高身長グループの最大身長」だけを更新しながら判定します。
この最大値を max_high とすると、

• max_high > s なら、この生徒は見上げる生徒
• もし s >= T なら高身長グループなので、max_high = max(max_high, s) で更新

とできます。

具体例

\(T=170\)、身長列が \([160, 175, 168, 172, 174]\) のとき：

• 1人目 160: 前に誰もいない → 見上げない。max_high=0（更新なし）
• 2人目 175: max_high=0 なので見上げない。高身長なので max_high=175
• 3人目 168: max_high=175 > 168 → 見上げる
• 4人目 172: max_high=175 > 172 → 見上げる。高身長なので max_high は変わらず 175
• 5人目 174: max_high=175 > 174 → 見上げる

答えは 3 人です。

アルゴリズム

1. max_high = 0（これまでに見た「高身長グループ」の最大身長）
2. ans = 0
3. 生徒を \(1\) 人目から順に身長 \(s\) を読むたびに：
   • もし max_high > s なら ans += 1（前に自分より高い高身長者がいる）
   • もし \(s \ge T\) かつ s > max_high なら max_high = s（高身長グループの最大値を更新）
4. ans を出力する

※「見上げるかどうかの判定」に本人が高身長グループかどうかは関係ないので、更新処理と判定処理を分けて考えると整理しやすいです。

計算量

• 時間計算量: \(O(N)\)（各生徒を1回ずつ処理）
• 空間計算量: \(O(1)\)（最大値と答えのみ）

実装のポイント

• \(N \le 10^6\) なので、Pythonでは入出力がボトルネックになりがちです。コードでは sys.stdin.buffer.read() で一括読み込みし、整数を高速にパースしています。

• max_high は「高身長グループ（\(S \ge T\)）」だけで更新する点が重要です。全員の最大値を取ってしまうと条件が変わって誤答になります。

• 条件は「厳密に高い」なので、判定は max_high > s（>= ではない）です。

  ソースコード

import sys

def ints_from_bytes(data: bytes):
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        sign = 1
        if data[i] == 45:  # '-'
            sign = -1
            i += 1
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield sign * num

def main():
    data = sys.stdin.buffer.read()
    it = ints_from_bytes(data)
    N = next(it)
    T = next(it)

    max_high = 0
    ans = 0
    for _ in range(N):
        s = next(it)
        if max_high > s:
            ans += 1
        if s >= T and s > max_high:
            max_high = s

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

---

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