概要

\(N\) 個の山の中で、標高が狭義に最大（他のすべての山より真に大きい）である山（独立峰）が存在するかを判定し、存在すればその標高を、存在しなければ \(0\) を出力する問題です。

考察

「独立峰」の定義を整理すると、次の2つの条件を同時に満たす山のことです：

1. その山の標高が全体の最大値である
2. その最大値を持つ山がちょうど1つだけである

例えば、山の標高が \([3, 5, 2, 5, 1]\) の場合、最大値は \(5\) ですが、\(5\) を持つ山が2つあるため、どちらも他のすべての山より真に大きいわけではありません（同じ標高の山が存在する）。よって独立峰は存在せず、答えは \(0\) です。

一方、\([3, 7, 2, 5, 1]\) の場合、最大値 \(7\) を持つ山は1つだけなので、山2が独立峰であり、答えは \(7\) です。

\(N = 1\) の場合は、比較対象が存在しないため、唯一の山が自動的に独立峰になります。これは「最大値が1つだけ」という条件で自然に処理できます。

この問題では \(N\) が最大 \(10^6\) と大きいですが、必要な操作は「最大値を求める」と「最大値の出現回数を数える」の2つだけなので、配列を1〜2回走査すれば十分です。特別なアルゴリズムは不要で、素朴なアプローチで問題なく間に合います。

アルゴリズム

1. 配列 \(A\) の最大値 max_val を求める
2. max_val が配列中に何回出現するかを数える
3. 出現回数が \(1\) なら max_val を出力、そうでなければ \(0\) を出力

具体例で確認：

• \(A = [3, 7, 2, 5, 1]\)：最大値 \(= 7\)、出現回数 \(= 1\) → 出力 7
• \(A = [3, 5, 2, 5, 1]\)：最大値 \(= 5\)、出現回数 \(= 2\) → 出力 0
• \(A = [42]\)：最大値 \(= 42\)、出現回数 \(= 1\) → 出力 42

計算量

• 時間計算量: \(O(N)\)
  • max(A) で配列を1回走査：\(O(N)\)
  • A.count(max_val) で配列を1回走査：\(O(N)\)
  • 合計 \(O(N)\)
• 空間計算量: \(O(N)\)（配列 \(A\) を保持するため）

実装のポイント

• Pythonの組み込み関数 max() と list.count() を使うことで、簡潔かつ高速に実装できます。これらはC言語レベルで実装されているため、\(N = 10^6\) 程度であれば十分高速です。

• 最大値を求めてからその出現回数を数えるという2段階の処理にすることで、ロジックがシンプルになります。1回の走査で「最大値」と「出現回数」を同時に管理することも可能ですが、この問題の制約ではどちらでも問題ありません。

• 狭義の不等号 \(>\)（>）と広義の不等号 \(\geq\)（>=）の違いに注意しましょう。この問題では狭義なので、最大値が複数あれば独立峰は存在しません。

  ソースコード

N = int(input())
A = list(map(int, input().split()))
max_val = max(A)
if A.count(max_val) == 1:
    print(max_val)
else:
    print(0)

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