概要

各地点について「左右の隣よりも高いか」を調べ、条件を満たす地点の個数を数える問題です。
山頂になりうるのは両隣を持つ地点だけなので、先頭と末尾を除いて順番に確認すれば求められます。

考察

山頂の定義は、地点 \(i\) が

• \(A_{i-1} < A_i\)
• \(A_i > A_{i+1}\)

を同時に満たすことです。
つまり、その地点の1つ左と1つ右だけを見れば判定できます。

たとえば

\(A = [1, 3, 2, 4, 4, 1]\)

のとき、

• \(i=2\) の値 \(3\) は、左の \(1\) より大きく、右の \(2\) より大きいので山頂
• \(i=3\) の値 \(2\) は山頂ではない
• \(i=4\) の値 \(4\) は右の \(4\) より厳密に大きくないので山頂ではない

このように、各地点は独立に判定できます。

重要な気づき

• 山頂かどうかの判定に必要なのは 隣接する3点だけ
• 先頭 \(i=1\) と末尾 \(i=N\) は片側に隣がないため、山頂にはなれない
• よって、\(i=2\) から \(i=N-1\) までを順に見ればよい

素朴なアプローチについて

この問題では、各地点について周囲を広く調べる必要はありません。
もし「その地点が周囲の多くの点より高いか」などと考えて余計な比較をしてしまうと無駄ですが、実際には左右1つずつ見るだけで十分です。

そのため、全体を1回走査するだけの \(O(N)\) で解けます。
\(N \leq 2 \times 10^5\) なので、この方法なら十分高速です。

アルゴリズム

1. 入力で \(N\) と配列 \(A\) を受け取る
2. 答えを表す変数 cnt を \(0\) で初期化する
3. \(i=1\) から \(N-2\)（0-indexed）まで順に見る
4. もし
   • \(A[i-1] < A[i]\)
   • \(A[i] > A[i+1]\)

を満たすなら cnt を \(1\) 増やす 5. 最後に cnt を出力する

0-indexed の配列で考えると、Python の a[i] は問題文の \(A_{i+1}\) に対応します。
そのため、ループは for i in range(1, n - 1): とするのが自然です。

計算量

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

実装のポイント

• 先頭と末尾は山頂になれないので、range(1, n - 1) で中央だけを調べます。

• 条件は「高い」ではなく 厳密に高い なので、<= ではなく < と > を使います。

• 入力が大きめなので、sys.stdin.buffer.read() を使う実装は高速で安定です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:1+n]
    
    cnt = 0
    for i in range(1, n - 1):
        if a[i - 1] < a[i] and a[i] > a[i + 1]:
            cnt += 1
    
    print(cnt)

if __name__ == "__main__":
    main()

---

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