概要

各山から左方向に見える山の数を求め、その合計を答える問題です。

考察

この問題では、各山 \(i\) に対して、左側の山の中で「見える」山の数 \(C_i\) を求め、すべての \(C_i\) の合計を出力します。

「見える」とは？

山 \(i\) から山 \(j\)（\(j < i\)）が見えるためには、次の2つの条件が必要です：

1. 山 \(j\) は山 \(i\) より厳密に高い：\(H_j > H_i\)
2. 山 \(j\) と山 \(i\) の間のすべての山 \(k\)（\(j < k < i\)）は、山 \(j\) よりも低い：\(H_k < H_j\)

この2つ目が重要で、「山 \(j\) が他の山に遮られているかどうか」を判定する必要があります。

素朴な解法とその問題

一番簡単な方法は、各山 \(i\) について、左から順に山 \(j\) を見ていき、上記の条件を愚直にチェックすることです。しかし、この方法の計算量は最悪の場合 \(O(N^2)\) となり、制約 \(N \leq 10^6\) では時間内に解けません（TLE）。

効率的な解法のアイディア

ある山 \(i\) から見える山というのは、それより左にあり、かつその間にそれ以上高い山がない山のことです。このような「最大値を保つ要素の管理」にはスタックが非常に有効です。

具体的には、左から順番に山を見ていき、今見ている山よりも低い山は以降見えなくなるため、スタックから取り除いてしまって良いのです。これにより、スタックの中には常に「今後も見える可能性のある山」だけが残ります。

つまり： - 各山 \(i\) に対して、スタックの中に残っている山の数が \(C_i\) になります。 - このスタックの操作は、各山を一度追加して一度削除するだけなので、全体で \(O(N)\) で処理可能です。

具体例

例えば入力が H = [3, 1, 4, 1, 5] のとき：

• 山1（高さ3）: スタックは空 → 見える山は0個
• 山2（高さ1）: スタック=[3] → 高さ3の山が見える → 1個
• 山3（高さ4）: スタック=[3,1] → 両方4以下なので削除 → スタック=[4] → 1個見える
• 山4（高さ1）: スタック=[4] → 1個見える
• 山5（高さ5）: スタック=[4,1] → 両方削除 → スタック=[5] → 0個見える

合計 = 0 + 1 + 1 + 1 + 0 = 3

アルゴリズム

1. 左から順に山を処理していきます。
2. 各山について：
   • スタックの末尾を見て、今見ている山の高さ以上なら取り出す（見えなくなるため）
   • スタックに残っている山の数が、その山から見える山の数
   • 現在の山の高さをスタックに追加
3. 各山ごとの見える山の数を合計して出力

このスタックは単調減少になるように管理します（上から小さい順）。そのため、deque を使い、末尾から操作するのが効率的です。

計算量

• 時間計算量: \(O(N)\)
  　各要素は高々1回スタックに追加され、1回削除されるだけなので、全体で線形時間。
• 空間計算量: \(O(N)\)
  　スタックに最大で \(N\) 個の要素が格納される。

実装のポイント

• スタックの操作は deque を使うと効率的（特に末尾操作）

• 各山について「見える山の数 = スタックの長さ」になる

• 同じ高さの山は見えないことに注意（\(H_j > H_i\) が必要）

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    H = list(map(int, data[1:]))

    # 左から右へ処理するためのスタック
    stack = deque()
    total = 0

    for i in range(N):
        h = H[i]
        # スタックの上から見て、現在の高さ以上なら取り除く（見える可能性がない）
        while stack and stack[-1] <= h:
            stack.pop()
        # 残っている山の数が、現在の山から見える山の数
        total += len(stack)
        # 現在の山の高さをスタックに追加
        stack.append(h)

    print(total)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。