概要

与えられたN個の山の標高から、他のすべての山より高い唯一の山（独立峰）があるかどうかを判定し、存在すればその標高を、存在しなければ0を出力する問題です。

考察

独立峰となるためには、以下の2つの条件を満たす必要があります： 1. その山が全体の中で最大の標高を持つ 2. 最大の標高を持つ山がただ1つだけ存在する

最大値が複数ある場合、どの山も「他のすべての山より高い」という条件を満たさないため、独立峰は存在しません。また、山が1つだけの場合は、その山自身が独立峰となります。

素朴なアプローチとして、各山について他のすべての山と比較する方法が考えられますが、これでは時間計算量が\(O(N^2)\)となり、制約\(N \leq 10^6\)では実行時間がかかりすぎます。

アルゴリズム

効率的な解法は以下の手順です： 1. 配列全体の最大値\(M\)を見つける 2. 最大値\(M\)が配列中に何回出現するか数える 3. 最大値の出現回数が1回なら\(M\)を出力、2回以上なら0を出力

山が1つの場合だけは特別ケースとして扱います。

計算量

• 時間計算量: \(O(N)\)
  • 最大値の探索に\(O(N)\)
  • 最大値のカウントに\(O(N)\)
• 空間計算量: \(O(N)\)
  • 入力配列を保持するため

実装のポイント

• 入力処理ではsys.stdin.read()を使って効率的に読み込む

• 山が1つだけの場合を最初にチェックする

• max()関数で最大値を求め、count()メソッドで出現回数を数える

• 最大値が複数ある場合に0を出力することを忘れない

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    
    if n == 1:
        print(A[0])
        return
        
    max_val = max(A)
    count_max = A.count(max_val)
    
    if count_max == 1:
        print(max_val)
    else:
        print(0)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。