概要

与えられた \(N\) 個の山の標高のうち、他のすべての山より高い「唯一の最大値」が存在するかを判定し、存在すればその値を、存在しなければ \(0\) を出力する問題です。

考察

問題文にある「独立峰」の条件とは、ある山の標高が他のすべての山よりも高いこと、つまり全体の 狭義の最大値 であることと同義です。

素朴なアプローチとして、各山 \(i\) について「他のすべての山 \(j\) と比較して高いか」を確認する方法が考えられます。しかし、この方法では二重ループとなり計算量が \(O(N^2)\) となります。制約が \(N \leq 10^6\) であるため、これではTLE（実行時間超過）になってしまいます。

そこで、視点を変えて「全体の最大値」に注目します。最大値が配列内にただ \(1\) つだけ存在すればそれが独立峰であり、\(2\) つ以上存在すれば独立峰はない、と判定できます。これにより、配列を走査するだけで効率よく答えを求めることができます。

アルゴリズム

1. 与えられた標高の配列 \(A\) の中から、最大値 \(M\) を見つけます。
2. 配列 \(A\) の中で、値が \(M\) と等しい要素の個数を数えます。
3. 個数がちょうど \(1\) 個であれば、\(M\) が唯一の最大値（独立峰）なので \(M\) を出力します。
4. 個数が \(2\) 個以上であれば、同じ高さの最大の山が複数あり独立峰は存在しないため、\(0\) を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 最大値の取得に \(O(N)\)、出現回数のカウントに \(O(N)\) かかります。配列を2回走査するだけなので、全体で \(O(N)\) となり \(N = 10^6\) でも十分に高速です。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の標高データをリストとしてメモリに保持するために使用します。

実装のポイント

• Pythonの組み込み関数を活用することで、最大値の取得は max(A)、要素のカウントは A.count(max_A) と非常に簡潔に記述できます。

• \(N \leq 10^6\) と入力サイズが比較的大きいため、通常の input() をループで回すのではなく、sys.stdin.read().split() を用いて入力を一括で読み込むことで、入力処理を高速化しTLEを防いでいます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    A = list(map(int, input_data[1:]))
    max_A = max(A)
    
    if A.count(max_A) == 1:
        print(max_A)
    else:
        print(0)

if __name__ == '__main__':
    main()

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