概要

手前から順に山を見ていき、「これまで見た中での最高標高」を更新した山だけを「見える山」として出力する問題です。

考察

山 \(i\) が見える条件は、「\(i\) より手前のすべての山の標高が \(H_i\) 未満」であることです。
これは言い換えると、手前の山の最大標高を \(M=\max(H_1,\dots,H_{i-1})\) とすると、山 \(i\) が見えるのは \(H_i > M\) のときだけ、ということになります（同じ高さ \(H_i = M\) でも隠れて見えない点に注意）。

素朴な方法が遅い理由

各 \(i\) について毎回 \(\max(H_1,\dots,H_{i-1})\) を計算すると、最大値を求めるのに \(O(i)\) かかり、全体で
\(O(1+2+\cdots+(N-1)) = O(N^2)\) となります。
\(N \le 2\times 10^5\) なので \(O(N^2)\) は間に合いません。

解決の方針

「手前の最大標高」を逐次更新すれば、各山を1回ずつ見るだけで判定できます。
つまり、左から順に見ていき、 - 現在の最大値 max_h より高い山が来たら見える → 答えに追加し、max_h を更新 - それ以外は見えない → 何もしない
とすればよいです。

具体例

\(H = [3, 2, 5, 5, 6]\) のとき： - 1番目 3：max_h=-1 より大 → 見える（max_h=3） - 2番目 2：max_h=3 より小 → 見えない - 3番目 5：max_h=3 より大 → 見える（max_h=5） - 4番目 5：max_h=5 と同じ → 見えない（同じ高さは隠れる） - 5番目 6：max_h=5 より大 → 見える（max_h=6）
よって答えは 1 3 5 です。

アルゴリズム

1. max_h を十分小さい値（例：-1）で初期化する。
2. 山を手前から順に（\(i=1\) から \(N\)）見ていく。
3. もし \(H_i > max_h\) なら山 \(i\) は見えるので、答えに \(i\) を追加し、max_h = H_i に更新する。
4. 最後に答えの番号を順に出力する。

この方法では「これまでの最大標高」だけを覚えておけばよく、各山の判定が \(O(1)\) でできます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（答えの配列を保存するため。判定自体は \(O(1)\) 追加メモリ）

実装のポイント

• 「同じ高さは見えない」ので条件は \(H_i \ge max_h\) ではなく \(H_i > max_h\) にする。

• 入力サイズが大きいので、Pythonでは sys.stdin.buffer.read() を使うと高速に読み取れる。

• 出力は見える山の番号をスペース区切りで1行にする。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    h = data[1:1+n]

    max_h = -1
    ans = []
    for i, hi in enumerate(h, 1):
        if hi > max_h:
            ans.append(i)
            max_h = hi

    sys.stdout.write(" ".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

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