概要

\(N\) 個の山について、それぞれの山より標高が「厳密に高い」山の数を求める問題です。

考察

まず、素朴な方法として「各山について、他のすべての山を一つずつ確認して自分より高いか調べる」という手順が考えられます。しかし、この方法では \(N\) 個の山それぞれに対して \(N\) 回の比較を行うため、全体で \(O(N^2)\) の計算量がかかります。今回の制約は \(N \leq 2 \times 10^5\) であるため、\(N^2\) は約 \(4 \times 10^{10}\) となり、実行制限時間に間に合いません。

そこで、標高をソート（並び替え）するというアプローチを考えます。 山を標高の高い順（降順）に並べたとします。例えば標高が [10, 30, 20, 30] の場合、降順にソートすると [30, 30, 20, 10] となります。

このとき、各要素のインデックス（0番目から数えた順番）に注目すると以下のことが分かります。 - 最初の 30 はインデックス 0：自分より高い山は 0 個 - 2番目の 30 はインデックス 1：自分より高い山は（厳密には） 0 個 - 20 はインデックス 2：自分より高い山は 2 個（30 が2つ） - 10 はインデックス 3：自分より高い山は 3 個（30 が2つ、20 が1つ）

つまり、降順にソートしたリストにおいて、ある標高が「最初に現れる位置（インデックス）」が、その標高よりも厳密に高い山の数と一致します。

アルゴリズム

1. 山の標高リスト \(A\) をコピーし、それを降順（大きい順）にソートしたリスト \(A_{sorted}\) を作成します。
2. \(A_{sorted}\) を先頭から走査し、各標高が「最初に何番目に現れたか」を辞書（ハッシュマップ）に記録します。
   • すでに辞書に登録されている標高は無視し、初めて登場した標高とそのインデックスのペアを保存します。
3. 元のリスト \(A\) の各要素について、辞書から対応するインデックス（自分より高い山の数）を引き出し、結果として出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 入力の読み込みに \(O(N)\)、ソートに \(O(N \log N)\)、辞書の作成と結果の構築に \(O(N)\) かかります。全体としてソートの部分が支配的になります。
• 空間計算量: \(O(N)\)
  • ソート済みのリストや、各標高のカウントを保持する辞書のために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が大きいため、Python の input() を繰り返すよりも sys.stdin.read().split() などで一括で読み込む方が効率的です。

• 辞書の活用: ある値に対して「自分より高い山の数」を \(O(1)\) で取得するために辞書を使用します。

• 重複の扱い: 全く同じ標高の山が複数ある場合、それらは互いに「自分より厳密に高い」とはみなさない点に注意が必要です。ソートしたリストで「最初に現れた位置」を記録することで、この条件を自然に満たすことができます。

  ソースコード

import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白で分割してリストにする
    # これにより、大量の入力データを高速に処理できる
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 1番目の要素は山の数 N
    n = int(input_data[0])
    # 2番目以降の要素は各山の標高 A_i
    a = list(map(int, input_data[1:n+1]))
    
    # 標高を降順（高い順）にソートしたリストを作成する
    # 降順に並べたとき、ある値が最初に現れるインデックスは、
    # その値よりも厳密に大きい要素の数と一致する
    a_sorted = sorted(a, reverse=True)
    
    # 各標高に対して、自分より高い山がいくつあるかを格納する辞書
    higher_than_count = {}
    for i, val in enumerate(a_sorted):
        # 既に辞書に登録されている（＝同じ標高の山が既に現れている）場合はスキップ
        if val not in higher_than_count:
            # 最初に現れた時のインデックス i が、自分より高い山の数
            higher_than_count[val] = i
    
    # 元の山の順番に従って、自分より高い山の数をリストに格納する
    result = [higher_than_count[val] for val in a]
    
    # 結果をスペース区切りで1行に出力する
    sys.stdout.write(" ".join(map(str, result)) + "\n")

if __name__ == "__main__":
    solve()

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