概要

\(N\) 人の生徒が出席番号順に並んでいるとき、自分より前にいる「高身長グループ（身長 \(T\) cm 以上）」のメンバーの中に、自分より厳密に身長が高い人がいる生徒（＝見上げる生徒）の人数を求める問題です。

考察

素朴なアプローチとその問題点

愚直に考えると、各生徒 \(i\) に対して、\(j < i\) を満たすすべての生徒 \(j\) を調べ、\(S_j \geq T\) かつ \(S_j > S_i\) となる \(j\) が存在するかチェックする方法があります。しかしこれは二重ループになるため、最悪 \(O(N^2)\) の時間がかかります。\(N\) が最大 \(10^6\) なので、\(10^{12}\) 回の操作となり TLE（制限時間超過）になります。

重要な気づき

生徒 \(i\) が「見上げる生徒」であるかどうかの判定条件を整理します：

自分より前にいる高身長グループ（\(S_j \geq T\)）のメンバーの中に、\(S_j > S_i\) を満たす人が 1人でもいる か？

これは、自分より前にいる高身長グループの中の最大身長さえ分かれば判定できます。なぜなら、最大身長が \(S_i\) より大きければ条件を満たす人が存在し、そうでなければ誰も条件を満たさないからです。

つまり、前から順番に走査しながら「これまでに見た高身長グループメンバーの身長の最大値」を1つの変数で管理すれば十分です。

具体例

\(N = 5, T = 160, S = [170, 155, 180, 165, 150]\) の場合：

生徒 \(i\)	\(S_i\)	高身長グループの最大値（\(i\) の前まで）	見上げる？
1	170	0	No（前に誰もいない）
2	155	170	Yes（\(170 > 155\)）
3	180	170	No（\(170 \not> 180\)）
4	165	180	Yes（\(180 > 165\)）
5	150	180	Yes（\(180 > 150\)）

答えは 3 人です。

アルゴリズム

1. 変数 max_tall を \(0\) で初期化する。これは「これまでに見た高身長グループメンバーの身長の最大値」を表す。
2. 生徒を出席番号 \(1\) から \(N\) まで順に走査する。
3. 各生徒 \(i\) について：
   • もし \(S_i < \) max_tall ならば、自分より前に身長が厳密に高い高身長グループのメンバーがいるので、カウントを \(+1\) する。
   • もし \(S_i \geq T\) かつ \(S_i > \) max_tall ならば、max_tall を \(S_i\) に更新する。
4. 最終的なカウントを出力する。

注意: 判定（\(S_i < \) max_tall）を行った後に max_tall を更新することで、「自分より前」という条件を正しく扱えます。max_tall が \(0\) のまま（まだ高身長グループのメンバーが現れていない場合）は、\(S_i \geq 1 > 0\) は成り立たないため、正しく「見上げる生徒ではない」と判定されます。

計算量

• 時間計算量: \(O(N)\)（生徒を1回走査するだけ）
• 空間計算量: \(O(N)\)（入力の配列分。最大値の管理は \(O(1)\)）

実装のポイント

• max_tall の初期値を \(0\) にすることで、高身長グループのメンバーがまだ1人もいない状態を自然に表現できます（身長は \(1\) 以上なので、\(S_i < 0\) は成り立たず誤カウントしません）。

• 判定と更新の順序が重要です。先に判定を行い、その後に max_tall を更新することで、自分自身を含めてしまうミスを防げます。

  ソースコード

N, T = map(int, input().split())
S = list(map(int, input().split()))

max_tall = 0  # max height among tall group members seen so far
count = 0

for i in range(N):
    if S[i] < max_tall:
        count += 1
    if S[i] >= T and S[i] > max_tall:
        max_tall = S[i]

print(count)

---

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