概要

手前から山を順番に見ていき、それまでの最大標高より高い山だけが「見える」という問題です。最大値を更新しながら1回走査するだけで解けます。

考察

問題の理解

山が「見える」条件を整理しましょう。

• 1番目の山：手前に山がないので必ず見える
• 2番目以降の山：手前にあるすべての山より標高が高い場合のみ見える

例えば、山の標高が [3, 5, 2, 6, 4] の場合： - 山1（標高3）：見える（最初の山） - 山2（標高5）：見える（3より高い） - 山3（標高2）：見えない（5以下なので山2に隠れる） - 山4（標高6）：見える（3, 5, 2のどれよりも高い） - 山5（標高4）：見えない（6以下なので山4に隠れる）

答えは 1 2 4 となります。

重要な気づき

「手前にあるすべての山より高い」という条件は、「手前にある山の最大標高より高い」と言い換えられます。

これにより、各山について過去のすべての山と比較する必要がなく、最大値だけを覚えておけばよいことがわかります。

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

もし各山について、それより手前のすべての山と比較すると： - 山2は山1と比較（1回） - 山3は山1, 2と比較（2回） - … - 山Nは山1〜N-1と比較（N-1回）

合計で \(1 + 2 + \cdots + (N-1) = \frac{N(N-1)}{2}\) 回の比較が必要となり、\(O(N^2)\) かかります。\(N = 2 \times 10^5\) では間に合いません。

解決策

「これまでの最大標高」を1つの変数で管理すれば、各山について定数時間で判定できます。

アルゴリズム

1. 変数 max_height を 0 で初期化（これまでの最大標高を記録）
2. 山を手前から順に（\(i = 1, 2, \ldots, N\)）見ていく
3. 各山について：
   • \(i = 1\)（最初の山）なら、必ず見えるので答えに追加
   • \(i \geq 2\) なら、\(H_i > \) max_height のとき答えに追加
   • max_height を \(\max(\)max_height\(, H_i)\) で更新
4. 答えに追加された山の番号を出力

計算量

• 時間計算量: \(O(N)\)
  • 各山を1回ずつ見て、定数時間の処理を行うだけ
• 空間計算量: \(O(N)\)
  • 入力の山の標高を格納する配列と、答えを格納する配列に使用

実装のポイント

• 0-indexed と 1-indexed の変換: Pythonの配列は0から始まるが、出力は1から始まる山の番号なので、i + 1 を出力する

• 最初の山の処理: i == 0 の条件で最初の山を特別扱いしているが、max_height = 0 かつ \(H_i \geq 1\) なので、実は H[i] > max_height の条件だけでも最初の山は必ず見えると判定される（コードの可読性のため明示的に書いている）

• print(*visible): リストの要素をスペース区切りで出力する便利な書き方

  ソースコード

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

visible = []
max_height = 0

for i in range(N):
    if i == 0 or H[i] > max_height:
        visible.append(i + 1)
    max_height = max(max_height, H[i])

print(*visible)

---

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