概要

与えられた \(N\) 個の地点の標高データから、両隣の地点よりも標高が厳密に高い地点（「山頂」）が何個あるかを数える問題です。

考察

「山頂」の定義は、ある地点 \(i\) の標高 \(A_i\) が、その左隣の標高 \(A_{i-1}\) と右隣の標高 \(A_{i+1}\) のどちらよりも大きいこと、すなわち \(A_{i-1} < A_i\) かつ \(A_i > A_{i+1}\) を満たすことです。

この問題を解く上でのポイントは以下の通りです： - 判定の範囲: 山頂になり得るのは、両隣に地点が存在する \(1 < i < N\) の範囲（2番目から \(N-1\) 番目まで）に限られます。 - 計算量: 地点の数 \(N\) は最大で \(2 \times 10^5\) です。各地点について両隣と比較する操作は定数時間で行えるため、端から順番に確認していけば制限時間内に十分間に合います。

例えば、標高が [1, 3, 2, 4, 1] の場合： - 2番目の「3」は、1 < 3 かつ 3 > 2 なので山頂です。 - 3番目の「2」は、3 > 2 かつ 2 < 4 なので山頂ではありません。 - 4番目の「4」は、2 < 4 かつ 4 > 1 なので山頂です。 このように、1つずつ条件を確認していく素直なアプローチで正解を導けます。

アルゴリズム

1. 標高のリスト \(A\) を読み込みます。
2. 山頂の個数を記録する変数 count を 0 で初期化します。
3. インデックス \(i\) を 1 から \(N-2\) まで（0-indexedの場合、2番目から \(N-1\) 番目の要素まで）順に動かしながら、以下の判定を行います。
   • もし \(A_{i-1} < A_i\) かつ \(A_i > A_{i+1}\) ならば、count を 1 増やす。
4. 最終的な count の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • リストを 1 回走査するだけなので、地点の数 \(N\) に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 入力された標高データをリストに格納するためのメモリが必要です。

実装のポイント

• インデックスの範囲: Python の range(1, n - 1) を使うことで、ちょうど「2番目の要素」から「後ろから2番目の要素」までを効率よくループさせることができます。

• 比較演算子: \(A_{i-1} < A_i > A_{i+1}\) のように、Python では比較演算子を繋げて書くことも可能ですが、コードの可読性のために and を使って明示的に条件を分けるのが一般的です。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    a = list(map(int, input_data[1:]))
    
    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__":
    solve()

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