概要

\(N\) 棟の建物が並んでおり、それぞれの建物が「自分より手前にあるどの建物よりも高い」場合に海から見えると判定されます。この条件を満たす建物の総数を求める問題です。

考察

ある建物 \(i\) が海から見えるかどうかを判定するためには、建物 \(1\) から建物 \(i-1\) までの高さの最大値 \(M\) を知る必要があります。

素朴なアプローチ

各建物 \(i\) について、毎回 \(H_1, \ldots, H_{i-1}\) の中から最大値を探すと、1つの建物につき最大で \(O(N)\) 回の比較が必要になります。建物は \(N\) 棟あるため、全体の計算量は \(O(N^2)\) となります。 本問題の制約は \(N \leq 2 \times 10^5\) であるため、\(O(N^2)\) のアルゴリズムでは計算回数が約 \(4 \times 10^{10}\) 回に達し、実行時間制限（TLE）に間に合いません。

効率的なアプローチ

建物を番号順（海に近い順）に見ていくとき、「これまでに現れた建物の高さの最大値」を記録しておくことで、効率的に判定が可能です。 1つ前の建物までの最大値を保持しておけば、新しい建物の高さ \(H_i\) とその最大値を比較するだけで、その建物が見えるかどうかを \(O(1)\) で判定できます。

例えば、建物の高さが \([12, 8, 10, 15]\) の場合を考えます。 1. 建物1（高さ12）：これまでの最大値は 0 なので、 \(12 > 0\) で見える。最大値を 12 に更新。 2. 建物2（高さ8）：\(8 \leq 12\) なので、見えない。最大値は 12 のまま。 3. 建物3（高さ10）：\(10 \leq 12\) なので、見えない。最大値は 12 のまま。 4. 建物4（高さ15）：\(15 > 12\) なので、見える。最大値を 15 に更新。

このように、リストを一度走査するだけで答えが求まります。

アルゴリズム

1. 現在の最大値を保持する変数 max_height を \(0\) で初期化します。
2. 海から見える建物の数を数える変数 count を \(0\) で初期化します。
3. 建物の高さ \(H_1, H_2, \ldots, H_N\) を順番に調べます。
   • もし現在の建物の高さ \(H_i\) が max_height よりも高ければ：
     • その建物は見えるので count を 1 増やします。
     • max_height を \(H_i\) で更新します。
4. 最終的な count の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 建物のリストを 1 回走査するだけなので、建物数 \(N\) に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 入力された建物の高さをすべてリストに格納する場合、\(O(N)\) のメモリを使用します。

実装のポイント

• 入力の高速化: \(N\) が大きいため、Python では sys.stdin.read().split() などを使って一括で入力を読み込むと高速です。

• 初期値の設定: 最初の建物は必ず見えるという条件がありますが、max_height = 0 としておけば、1番目の建物（\(H_1 \geq 1\)）で必ず H_i > max_height が真となり、正しく処理されます。

  ソースコード

import sys

def main():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 建物の棟数
    n = int(input_data[0])
    # H: 各建物の高さのリスト
    h_list = list(map(int, input_data[1:]))
    
    count = 0
    max_height = 0
    
    # 各建物について、これまでの最大値と比較する
    for h in h_list:
        if h > max_height:
            count += 1
            max_height = h
            
    # 海から見える建物の個数を出力
    print(count)

if __name__ == "__main__":
    main()

この解説は gemini-3-flash-preview によって生成されました。