概要

各地点のうち、左右の隣より標高が高い地点（山頂）の数を数える問題です。
配列を1回走査して、各中央要素 \(A_i\) が \(A_{i-1} < A_i > A_{i+1}\) を満たすか判定すれば求められます。

考察

山頂の条件は「ある地点 \(i\) が、左隣より高く、かつ右隣より高い」です。
つまり、地点 \(i\) が山頂かどうかは \(A_{i-1}, A_i, A_{i+1}\) の3つだけ を見れば判定できます。

ここで重要なのは次の2点です。

• 端の地点（\(i=1, N\)）は隣が片側しかないため、山頂になりえない
  → 判定対象は \(2\) 番目から \(N-1\) 番目（0-indexなら 1 から N-2）だけ。
• 各地点の判定は独立で、1回ずつチェックすれば十分
  → 全体を1周するだけで答えが出る。

この問題に対して、例えば「山の形をまとめる」「区間ごとに最大値を探す」といった複雑な方法は不要です。
各地点をその場で判定するだけなので、最も素直な線形走査が最適です。

例: \(A=[1,3,2,4,4,1]\) のとき
- \(i=2\)（値3）: \(1<3\) かつ \(3>2\) → 山頂
- \(i=3\)（値2）: \(3<2\) が偽 → 山頂でない
- \(i=4\)（値4）: \(2<4\) かつ \(4>4\) は後半が偽（等しい） → 山頂でない
- \(i=5\)（値4）: \(4<4\) が偽 → 山頂でない
よって個数は 1。

アルゴリズム

1. 入力で \(N\) と配列 \(A\) を受け取る。
2. count = 0 を用意する。
3. i = 1 から N-2（0-index）までループする。
4. 条件 A[i-1] < A[i] and A[i] > A[i+1] を満たせば count += 1。
5. 最後に count を出力する。

提示コードはこの手順をそのまま実装しています。

計算量

• 時間計算量: \(O(N)\)
  各地点を高々1回ずつ判定するため。
• 空間計算量: \(O(1)\)（入力配列を除く補助領域）
  使う追加変数は count など定数個だけです。

実装のポイント

• Pythonでは0-indexなので、判定範囲は for i in range(1, N-1): が正しいです。

• 比較は 厳密不等号（<, >）である点に注意。>= や <= を使うと誤答になります。

• 入力サイズが大きめなので、sys.stdin.readline を使うと安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))

    count = 0
    for i in range(1, N - 1):
        if A[i - 1] < A[i] and A[i] > A[i + 1]:
            count += 1

    print(count)

if __name__ == "__main__":
    main()

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