【Python】転置数とは？求め方を解説

Aru

競技プログラムをやっていると頻繁に使う転置数の問題に出くわします。転置数は、数列がどれだけ乱れているかを示す指標で、「手前にある自身より大きな値の数の和」です。この記事では、転置数とは何かについて説明し、Pythonで転置数を高速に求める方法を示します。

Contents

転置数とは
転置数の意味
転置数の応用
- 1. ソートの困難さの目安
- 2. パズル（15パズルなど）
転置数に求め方（BITを使う）
- 手順の概要
- Pythonによる実装
まとめ

転置数とは

転置数（Inversion Number）は、ある数列がどれだけ「元の順序」から乱れているかを示す指標で、簡単に言えば、「逆順になっているペアの数」です。

逆順のペアの数は自分より大きな数値が手前に何個あるかと一致します。

例えば、数列 [3, 1, 2] の場合、3より大きな値は手前に0個、1より大きな値は3が１つ、2より大きな値は3の１つで合計２になります。

つまり、転置数は 2 になります。

転置数の意味

より形式的に説明すると、転置数は次のように定義されます

数列 a = [a₁, a₂, ..., aₙ] に対して、i < j かつ aᵢ > aⱼ となるような組 (i, j) の個数

「i < j なのに aᵢ > aⱼ である」というのが「順番が逆になっている」ことを意味しています。

例：順序と転置数の関係

数列	転置数
[1, 2, 3, 4]	0
[2, 1, 3, 4]	1
[4, 3, 2, 1]	6
[3, 1, 2, 4]	3

最も転置数が小さいのは昇順（=整列済み）のときで 0、最大値は降順のときで n(n−1)/2 になります（n は数列の長さ）。

転置数の応用

転置数を利用する応用としては以下のようなものがあります。

1. ソートの困難さの目安

たとえば、挿入ソート（insertion sort）の交換回数は転置数に比例します。つまり、転置数が多いほど、より多くの交換が必要になります。転置数は、ソートの「困難さ」を示す一つの目安として使うことができます。

2. パズル（15パズルなど）

スライディングパズルの解ける/解けない判定条件に、転置数の偶奇が関わる場合があります。
例えば、15パズルでは「転置数 + 空白の段数」が偶数か奇数かによって、解の存在が判定できます。

応用自体は少ないですが、競技プログラミングの世界では結構出題されます（どちらかというと転置数を高速に求めるアルゴリズムを問う問題ですが）。転置数をどうやって求めるかを覚えておくと良いと思います。

転置数に求め方（BITを使う）

転置数は愚直に求めるとO(n²) の計算量になり、巨大なサイズの数列に対しては現実的な解法ではありません。

転置数を高速に求める場合、Binary Indexed Tree（BIT、別名 Fenwick Tree）やSegment Treeがよく使われます。これらのアルゴリズムを使うことで転置数を O(n log n) で求めることができます。この記事では、転置数をBITを使って求める方法を解説します。

手順の概要

必要な場合は、数列の要素を「1 から n までの範囲」に圧縮（座標圧縮）
先頭から要素を処理し、その要素より大きな値がいくつ出現しているかをBITで求める
全ての要素の結果を合計すれば、それが転置数になる

Pythonによる実装

以下は、BITを使って転置数を求めるPythonコードです。このプログラムは、AtCoderの問題の「J-転置数」の解答になります。

# fenwick tree
class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l - 1)
    

n = int(input())
a = list(map(int, input().split()))
max_a = max(a)
bit = FenwickTree(max_a)


cnt= 0
for i in range(n):
    cnt += bit.range_sum(a[i] + 1, max_a)
    bit.add(a[i], 1)

print(cnt)