概要

数列の中で、両隣よりも厳密に高い地点（山頂）の個数を数える問題です。

考察

この問題は非常にシンプルで、各地点について「山頂」の条件を満たすかどうかを1つずつ確認すればよいです。

山頂の定義を正確に理解する：

地点 \(i\) が山頂であるとは、以下の2つの条件を同時に満たすことです： - \(A_{i-1} < A_i\)（左隣より厳密に高い） - \(A_i > A_{i+1}\)（右隣より厳密に高い）

具体例で確認：

例えば、標高データが 1 3 2 4 1 の場合（\(N = 5\)）：

地点 \(i\)	\(A_{i-1}\)	\(A_i\)	\(A_{i+1}\)	山頂？
2	1	3	2	✅ (\(1 < 3\) かつ \(3 > 2\))
3	3	2	4	❌ (\(3 < 2\) が不成立)
4	2	4	1	✅ (\(2 < 4\) かつ \(4 > 1\))

よって山頂は 2個 です。

注意点： - 最初の地点（\(i = 1\)）と最後の地点（\(i = N\)）は、両隣が存在しないため山頂にはなり得ません。 - 等号（\(=\)）では山頂にならないことに注意してください。条件は厳密な不等号です。

この問題では \(N \leq 2 \times 10^5\) なので、単純に全地点を1回ずつ調べる \(O(N)\) の方法で十分高速に解けます。特別なアルゴリズムやデータ構造は不要です。

アルゴリズム

1. \(N\) と標高の配列 \(A\) を入力から読み取る。
2. カウンタ count を \(0\) に初期化する。
3. \(i = 1, 2, \ldots, N-2\)（0-indexed）について、以下を確認する：
   • \(A[i-1] < A[i]\) かつ \(A[i] > A[i+1]\) であれば count を \(1\) 増やす。
4. count を出力する。

※ 問題文では1-indexed で \(i = 2, 3, \ldots, N-1\) を調べますが、Pythonの0-indexedでは \(i = 1, 2, \ldots, N-2\) に対応します。

計算量

• 時間計算量: \(O(N)\) — 配列を1回走査するだけです。
• 空間計算量: \(O(N)\) — 標高データを配列として保持します。

実装のポイント

• Pythonの range(1, N - 1) は \(1\) から \(N - 2\) までを生成するため、最初と最後の地点を自然に除外できます。

• 条件判定では <= ではなく < と > を使い、厳密な不等号であることを忘れないようにしましょう。

  ソースコード

N = int(input())
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)

---

この解説は claude4.6opus-thinking によって生成されました。