概要

\(N\) 個の山それぞれについて、自分より標高が厳密に高い山の数を効率的に数える問題です。

考察

素朴なアプローチとその問題点

最も単純な方法は、各山 \(i\) について、他のすべての山と標高を比較することです。

for i in range(N):
    count = 0
    for j in range(N):
        if A[j] > A[i]:
            count += 1

この方法は \(O(N^2)\) の時間がかかります。\(N\) が最大 \(2 \times 10^5\) の場合、\(4 \times 10^{10}\) 回の比較が必要となり、制限時間内に終わりません（TLE）。

重要な気づき

「自分より高い山の数」は、言い換えると「全体の中で自分の標高より大きい値の個数」です。

配列をソートしておけば、二分探索を使って「ある値より大きい要素の個数」を高速に求められます。

具体例

例えば、標高が \([3, 1, 4, 1, 5]\) の場合を考えます。

ソートすると \([1, 1, 3, 4, 5]\) になります。

• 山1（標高3）：3より大きいのは \([4, 5]\) の2個
• 山2（標高1）：1より大きいのは \([3, 4, 5]\) の3個
• 山3（標高4）：4より大きいのは \([5]\) の1個
• 山4（標高1）：1より大きいのは \([3, 4, 5]\) の3個
• 山5（標高5）：5より大きいのは 0個

答えは \([2, 3, 1, 3, 0]\) です。

アルゴリズム

1. 配列のソート: 元の配列 \(A\) をソートした配列 sorted_A を作成
2. 二分探索で個数を求める: 各山の標高 \(a\) について
   • bisect_right(sorted_A, a) で「\(a\) 以下の要素の個数」を求める
   • \(N\) からこの値を引くと「\(a\) より大きい要素の個数」が得られる

bisect_right の動作

bisect_right(sorted_A, a) は、ソート済み配列に \(a\) を挿入するとき、\(a\) と等しい要素があればその右側に挿入する位置を返します。

つまり、\(a\) 以下の要素の個数を返します。

例：sorted_A = [1, 1, 3, 4, 5] のとき - bisect_right(sorted_A, 3) → 3（位置0,1,2の3つが3以下） - よって、3より大きい要素の数は \(5 - 3 = 2\)

計算量

• 時間計算量: \(O(N \log N)\)

  • ソート: \(O(N \log N)\)
  • 各要素に対する二分探索: \(O(\log N) \times N = O(N \log N)\)

• 空間計算量: \(O(N)\)

  • ソート済み配列と結果配列の保持に必要

実装のポイント

1. bisect_right を使う理由: 同じ標高の山は「厳密に高い」に含まれないため、bisect_right で「以下」の個数を求めます。bisect_left を使うと「未満」の個数になり、同じ標高の山も「より高い」としてカウントされてしまいます。

2. 元の順序を保持: ソートは別の配列で行い、元の配列 \(A\) の順序は変えません。出力は入力の順序で行う必要があるためです。

3. 高速な入出力: \(N\) が大きい場合に備えて、sys.stdin.readline を使用して入力を高速化しています。

   ソースコード

import sys
from bisect import bisect_right

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    
    # ソートされた配列を作成
    sorted_A = sorted(A)
    
    # 各山について、その山より標高が厳密に高い山の数を求める
    result = []
    for a in A:
        # bisect_rightで、a以下の要素の数を求める
        # N - bisect_right(sorted_A, a) で、aより大きい要素の数を求める
        count = N - bisect_right(sorted_A, a)
        result.append(count)
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

---

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