概要

海から見たとき、手前の建物に完全に隠れない建物の個数を数える問題です。これは「今まで見た最大の高さを超える建物が何個あるか」を数えることで解けます。

考察

重要な気づき

建物 \(i\) が海から見えるかどうかは、それより手前にあるすべての建物の高さの最大値 \(M\) と比較して、\(H_i > M\) かどうかで決まります。

具体例で考えてみましょう。建物の高さが \([3, 1, 4, 1, 5]\) の場合：

建物番号	高さ	手前の最大高さ	見える？
1	3	0（手前に建物なし）	○
2	1	3	× (1 ≤ 3)
3	4	3	○ (4 > 3)
4	1	4	× (1 ≤ 4)
5	5	4	○ (5 > 4)

答えは 3個（建物1, 3, 5）です。

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

各建物 \(i\) について、建物 \(1\) から \(i-1\) までの最大値を毎回計算すると、計算量は \(O(N^2)\) になります。\(N \leq 2 \times 10^5\) の場合、これでは間に合いません。

解決策

最大値を毎回計算し直すのではなく、これまでの最大値を変数で保持しながら更新していくことで、各建物の判定を \(O(1)\) で行えます。

アルゴリズム

1. max_height = 0（これまでの最大高さ）と count = 0（見える建物の数）を初期化
2. 建物を海側から順に（\(i = 1, 2, \ldots, N\)）見ていく
3. 各建物について：
   • \(H_i > \text{max\_height}\) なら、その建物は見えるので count を1増やす
   • max_height を \(\max(\text{max\_height}, H_i)\) で更新
4. 最終的な count を出力

このアルゴリズムは、「今まで見た中での最大値を更新しながら、その最大値を超えた回数を数える」という処理になっています。

計算量

• 時間計算量: \(O(N)\)
  • 各建物を1回ずつ見るだけで済むため
• 空間計算量: \(O(N)\)
  • 入力の配列 \(H\) を保持するため
  • （入力を逐次処理すれば \(O(1)\) も可能）

実装のポイント

• max_height の初期値を \(0\) にすることで、建物1は必ず \(H_1 > 0\) となり、自動的に「見える」と判定されます（問題の制約で \(H_i \geq 1\)）

• 条件分岐の中で max_height を更新しているのは、見える建物だけが新しい「遮り」になるためです。実際には見えない建物で更新しても結果は同じですが、見える建物でのみ更新する方が直感的です

  ソースコード

N = int(input())
H = list(map(int, input().split()))

count = 0
max_height = 0

for h in H:
    if h > max_height:
        count += 1
        max_height = h

print(count)

---

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