概要

配列を隣接要素のスワップのみでソートするために必要な最小操作回数を求める問題です。これは「転倒数（inversion count）」を求める問題に帰着されます。

考察

重要な気づき

隣り合う2つの要素を入れ替える操作は、「バブルソート」で行う操作と同じです。バブルソートでソートが完了するまでの交換回数は、配列の転倒数に等しいことが知られています。

転倒数とは？ 配列において、\(i < j\) かつ \(A_i > A_j\) となるペア \((i, j)\) の個数です。

例えば、配列 \([3, 1, 2]\) の場合：

• \((1, 2)\): \(A_1 = 3 > A_2 = 1\) → 転倒ペア
• \((1, 3)\): \(A_1 = 3 > A_3 = 2\) → 転倒ペア
• \((2, 3)\): \(A_2 = 1 < A_3 = 2\) → 転倒ペアではない

よって転倒数は \(2\) です。実際、\([3,1,2] \to [1,3,2] \to [1,2,3]\) と2回の隣接スワップでソートできます。

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

全てのペア \((i, j)\) について \(i < j\) かつ \(A_i > A_j\) かをチェックする方法では、ペアの総数が \(\frac{N(N-1)}{2}\) 個あるため、\(O(N^2)\) の計算量がかかります。\(N \leq 2 \times 10^5\) の制約では、これはTLE（時間超過）になります。

解決策

マージソートを利用すると、ソートを行いながら \(O(N \log N)\) で転倒数を数えることができます。

アルゴリズム

マージソートの「マージ」の過程で転倒数をカウントします。

マージソートでは、配列を左半分と右半分に分割し、それぞれをソートしてからマージします。マージの際に：

1. 左半分の配列から要素を取る場合：転倒は発生しない
2. 右半分の配列から要素を取る場合：その要素より大きい左半分の残り要素全てと転倒ペアを形成

例: left = [2, 4], right = [1, 3] をマージ

- right[0]=1 を取る → left の残り要素 [2,4] より小さい → 転倒数 +2
- left[0]=2 を取る → 転倒数 +0
- right[1]=3 を取る → left の残り要素 [4] より小さい → 転倒数 +1
- left[1]=4 を取る → 転倒数 +0
合計: 3

計算量

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

  • マージソートの計算量と同じです
  • 配列を \(\log N\) 回分割し、各レベルで合計 \(O(N)\) の処理を行います

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

  • マージ時に一時配列を使用するため

実装のポイント

1. 再帰の終了条件: 配列の長さが1以下の場合は、転倒数0でそのまま返す

2. マージ時のカウント: 右側の配列から要素を選んだとき、左側の配列で「まだマージされていない要素の個数」を転倒数に加算する（len(left) - i）

3. 安定ソートの条件: left[i] <= right[j] のように等号を含めることで、同じ値の場合は左側を優先し、余計なカウントを防ぐ（この問題では順列なので同じ値は存在しませんが、一般的な実装として重要）

ソースコード

def merge_sort_count(arr):
    if len(arr) <= 1:
        return arr, 0
    
    mid = len(arr) // 2
    left, left_inv = merge_sort_count(arr[:mid])
    right, right_inv = merge_sort_count(arr[mid:])
    
    merged = []
    inv_count = left_inv + right_inv
    i = j = 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_count += len(left) - i
            j += 1
    
    merged.extend(left[i:])
    merged.extend(right[j:])
    
    return merged, inv_count

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    _, inversions = merge_sort_count(A)
    print(inversions)

solve()

---

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