概要

各山から左方向に見える山の数を条件に従って数え、その総和を求める問題です。

考察

素朴なアプローチでは、各山 \(i\) について、左側の全ての山 \(j\) (\(j < i\)) を調べながら条件を満たすかチェックすると、最悪の場合 \(O(N^2)\) の時間がかかり、\(N\) が最大 \(10^6\) の制約では実行時間制限に間に合いません。効率的な解法が必要です。

重要な観察は、山 \(i\) から見える山は、山 \(i\) より左側の山の中で、単調減少する「候補」の列になっていることです。具体的には、山 \(i\) の左側で、より高い山が見えるたびに、それより低い山は遮られて見えなくなるため、スタックを使って管理することで効率的に処理できます。

アルゴリズム

スタックを用いて、左から順に山を処理します。各山 \(i\) について、以下の操作を行います： 1. スタックの先頭が現在の山 \(H_i\) 以下である限り、それらをポップします（これらは現在の山より低く、以降の山からは見えなくなるため）。 2. スタックのサイズ（= 現在の山より高く、条件を満たす山の数）を答えに加算します。 3. 現在の山 \(H_i\) をスタックにプッシュします。

この方法では、スタックには常に「単調減少」する山の標高が保持されます。各山がスタックに追加・削除される回数は高々1回ずつなので、効率的に処理できます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• スタックには山の標高を保存します。

• スタックからポップする際の条件は stack[-1] <= H[i] です（等号を含むことに注意：同じ高さの山は見えないため）。

• 各ステップでスタックのサイズを加算することで、現在の山から見える山の数を得られます。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    H = list(map(int, data[1:1+n]))
    
    stack = []
    total = 0
    for i in range(n):
        count = 0
        while stack and stack[-1] <= H[i]:
            stack.pop()
            count += 1
        total += len(stack)
        stack.append(H[i])
    
    print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。