概要

\(N\) 個の山が並んでおり、ある山が「見える」ための条件は、その山より手前にあるすべての山よりも標高が高いことです。この条件を満たす山の番号をすべて抽出する問題です。

考察

ある山 \(i\) が見えるかどうかを判定するには、定義通りに考えると「\(1\) 番目から \(i-1\) 番目までのすべての山の標高」を確認する必要があります。

しかし、毎回すべての山を確認すると、計算量は以下のようになります： - 1番目の山の判定：0個確認 - 2番目の山の判定：1個確認 - 3番目の山の判定：2個確認 - … - \(N\) 番目の山の判定：\(N-1\) 個確認

全体の比較回数はおおよそ \(\frac{N^2}{2}\) 回となり、今回の制約である \(N = 2 \times 10^5\) では \(2 \times 10^{10}\) 回程度の計算が必要です。一般的なプログラミングコンテストの実行時間制限（2秒間）では、\(10^8\) 回程度の計算が限界であるため、この「素朴な方法」では実行時間制限超過（TLE）になってしまいます。

ここで、「手前にある山の中で最も高い山の標高」さえ分かれば、すべての山と比較する必要がないことに気づきます。 山 \(i\) が見える条件は、以下のように言い換えられます。 - \(H_i > (\text{1番目から } i-1 \text{ 番目までの山の中の最大標高})\)

手前から順に山を見ていきながら、それまでに現れた標高の最大値を更新し続けることで、各山に対してわずか 1 回の比較で判定が可能になります。

アルゴリズム

「これまでに現れた山の最大標高」を保持する変数（current_max_height）を用意します。

1. current_max_height を \(0\) で初期化します。
2. \(i = 1\) から \(N\) まで、順番に以下の処理を行います。
   • もし現在の山の標高 \(H_i\) が current_max_height よりも高い場合：
     • その山は「見える」ので、番号 \(i\) を記録します。
     • current_max_height を \(H_i\) に更新します。
   • そうでない（\(H_i\) が current_max_height 以下）場合：
     • その山は見えないので、何もしません。
3. 記録した番号を順番に出力します。

計算量

• 時間計算量: \(O(N)\)
  • 山の数 \(N\) に対して、手前から順に 1 回ずつ確認するだけなので、標高の比較回数は \(N\) 回です。\(N=2 \times 10^5\) でも十分に高速に動作します。
• 空間計算量: \(O(N)\)
  • 入力された標高のリストや、答えとなる山の番号を格納するリストに \(O(N)\) のメモリを使用します。

実装のポイント

• 1-based indexing: 問題文では山の番号が 1 から始まっているため、プログラム内での 0 番目の要素が「山の番号 1」に対応することに注意して出力します。

• 最大値の更新: current_max_height を更新することで、常に「その山より手前にある最も高い山」との比較が可能になります。

• 高速な入出力: Pythonの場合、sys.stdin.read().split() を使うことで大量の入力を高速に読み込むことができます。また、print(*list) とすることで、リストの中身をスペース区切りで簡潔に出力できます。

  ソースコード

import sys

def solve():
    # 入力を標準入力からすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    h = list(map(int, input_data[1:]))
    
    visible_mountains = []
    current_max_height = 0
    
    for i in range(n):
        # 現在の山の標高がこれまでの最大標高よりも高い場合、その山は見える
        if h[i] > current_max_height:
            visible_mountains.append(i + 1)
            current_max_height = h[i]
            
    # 見える山の番号をスペース区切りで出力
    print(*(visible_mountains))

if __name__ == '__main__':
    solve()

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