概要

与えられた順列をソートするために必要な、隣接要素の交換回数の最小値を求めます。

考察

この問題は、配列を昇順にソートするために必要な転倒数（inversion）を数える問題です。

転倒数とは、「左にあるべき数よりも右に小さな数がある」という不適切なペアの数です。例えば、配列 \([3, 1, 2]\) では、\((3, 1)\) と \((3, 2)\) の2つの転倒があります。

隣接する2つの要素を入れ替える操作は、ちょうど1回の転倒を解消する操作に対応します。したがって、全体をソートするには、転倒数の分だけ操作が必要になります。

ナイーブな方法（バブルソートのように隣接交換をシミュレート）では、最悪ケースで \(O(N^2)\) かかり、制約 \(N \leq 2 \times 10^5\) に対してはTLEになってしまいます。

そこで、効率的に転倒数を数える方法として、マージソートを使ったアルゴリズムを使います。これは、分割統治法の一種で、ソートしながら転倒数もカウントできます。

アルゴリズム

転倒数をマージソートによって数えるアルゴリズムの流れは以下の通りです。

1. 配列を再帰的に半分に分割していきます。
2. 分割された左部分配列、右部分配列について、それぞれソート済みとし、それらをマージします。
3. マージ中に、右側の要素が左側の要素より前に来る場合、その時点で左側の残り要素数分だけ転倒が存在していることがわかります。
4. このときのカウントを合計することで、全体の転倒数が求められます。

たとえば、左が \([1, 4, 5]\)、右が \([2, 3]\) のとき、最初に右の 2 を選ぶときに、左の 4 と 5 が後に来ることになるので、2つの転倒をカウントします。

このようにして、マージソートの過程で効率的に転倒数を数えることができます。

計算量

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

実装のポイント

• merge_sort_and_count_inversions 関数は再帰的に呼び出され、マージ時に転倒数をカウントします。
• 左側の残り要素数 len(left) - i を加算するのがポイントです。
• Python では再帰の深さに制限があるため、非常に大きな \(N\) では注意が必要ですが、今回の制約では問題ありません。

ソースコード

def merge_sort_and_count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0

    mid = len(arr) // 2
    left, inv_left = merge_sort_and_count_inversions(arr[:mid])
    right, inv_right = merge_sort_and_count_inversions(arr[mid:])
    
    merged = []
    i = j = 0
    inv_split = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            inv_split += len(left) - i
            j += 1
            
    merged.extend(left[i:])
    merged.extend(right[j:])
    
    return merged, inv_left + inv_right + inv_split

n = int(input())
a = list(map(int, input().split()))

_, inversions = merge_sort_and_count_inversions(a)
print(inversions)

---

この解説は qwen3-coder-480b によって生成されました。