コンテンツにスキップ

転倒数のリンク集

転倒数について、参考になる記事や資料をまとめました。

数列 AA の転倒数は、i<ji < j かつ Ai>AjA_i > A_j を満たす組 (i,j)(i, j) の個数です。左から順に「自分より前にあって自分より大きい要素の個数」を BIT で数えて足していくと O(Nlog⁡N)O(N \log N) で求まります。マージソートの途中で、左半分と右半分にまたがる組を数える方法でも O(Nlog⁡N)O(N \log N) です。転倒数は、隣どうしの入れ替えで数列を昇順にするときの最小の回数(バブルソートの交換回数)に一致します。値の異なる隣どうしを入れ替えると転倒数はちょうど 11 増えるか 11 減り、昇順の列の転倒数は 00 だからです。

BIT を使う方法では値をそのまま添字にするので、値が大きいときや負の値があるときは座標圧縮が必要です。同じ値の組は転倒に数えないので、「自分以下の値の個数」を引くようにします。また、転倒数は最大で N(N−1)/2N(N-1)/2 になり、N=105N = 10^5 でも 32 bit 整数に収まらないので、答えは 64 bit 整数で持ってください。BIT そのものについては BIT のリンク集 も見てください。

  • 転倒数(pocala-kyopro、Scrapbox)
    • 例の数列で BIT に 1 を足していく様子を表で追いながら、「これまでに見た個数 − 自分以下の個数」で自分より前にある大きい値の個数が求まることを説明しています。C++ の実装つきです。
    • 値が 11 以上 NN 以下(順列)であることを前提にしていて、座標圧縮には触れていません。
  • BITで転倒数を求める(wisteria0410ss、Qiita)
    • BIT による方法を擬似コードで説明し、座標圧縮で BIT の長さを値の種類数に抑える方法も書いています。最後に、転倒数がバブルソートの交換回数に一致する理由を補足しています。
    • 擬似コードで、答えに tjt_j を足すだけの行に「BITを使ってO(log N)」というコメントがあります。BIT を使うのは 1 つ上の bb に 11 を足す行で、コメントの位置がずれています。
  • Binary Indexed Tree (BIT) 総まとめ!区間加算や二次元BITまで(アルゴリズムロジック)
    • BIT の記事の一節で、転倒数の手順を短くまとめています。値が 11 以上であることを前提にしているので、00 があるときは 11 を足すか座標圧縮してから使ってください。
  • 転倒数(taq225algo、Scrapbox)
    • 列を半分に分けて「左半分の転倒数 + 右半分の転倒数 + またがる組の数」で求める分割統治と、座標圧縮した BIT による方法の両方を、Python の実装つきで説明しています。
    • BIT の節の式 tk+1′=∑v<ak+1B[v]t'_{k+1} = \sum_{v < a_{k+1}} B[v] は、tj′t'_j の定義(ai≤aja_i \le a_j の個数)に合わせると v≤ak+1v \le a_{k+1} が正しいです。コードは正しく bit.sum(x+1) で、等しい値まで数えています。
  • Count Inversions of an Array(GeeksforGeeks、英語)
    • 全組を調べる O(n2)O(n^2) の方法と、マージソートでまたがる組を数える O(nlog⁡n)O(n \log n) の方法を、C++・Java・Python などのコードで示しています。
    • コードは転倒数を int で持っているので、そのまま使うと大きな nn であふれます。

転倒数そのものを扱う講座はまだありませんが、関連する講座があります。

  • 区間クエリのためのモノイド設計
    • 「8.1 転倒数」の節で、順列の転倒数を区間和のセグメント木で求める方法を 2 通り説明しています。添字の順に処理して値を添字にする方法と、値の順に処理して位置を添字にする方法です。一般の列のときの座標圧縮や、同じ値の扱いにも触れています。
  • inversion-counting.hpp(Nyaan’s Library)
    • 座標圧縮つきで転倒数を long long で返す inversion_counting と、隣どうしの入れ替えで列 vv を列 ww にする最小回数を返す swap_distance があります。ドキュメントはなく、コード中のコメントだけです。
  • Static Range Inversion Query(hitonanode’s library)
    • 数列の区間 [l,r)[l, r) の転倒数にオンラインで答える実装で、時間 O((N+Q)N)O((N + Q)\sqrt{N})、空間 O(NN)O(N\sqrt{N}) です。N=105N = 10^5 で約 128 MB 使うと書かれています。
  • 転倒 (数学)(日本語版 Wikipedia)
    • 転倒・転倒数・転倒ベクトルの定義と、置換の弱順序を扱う短い記事です。バブルソートや置換の符号との関係は書かれていません。
  • Inversion (discrete mathematics)(英語版 Wikipedia)
    • 転倒の定義、転倒集合、Lehmer code などの転倒を表すベクトル、4 文字の順列すべての表、置換の弱順序まで扱っています。比較ソートを改造すると O(nlog⁡n)O(n \log n) で数えられることにも一言触れています。
  • Point Update Range Sum(USACO Guide)
    • BIT とセグメント木の章の中に「Inversion Counting」の節があり、転倒数の問題の一覧もあります。C++ のコードは BIT ではなく、順序統計木(__gnu_pbds の tree)を使っています。
    • Java と Python のコードは値の上限 10710^7 の BIT をそのまま使っていて、座標圧縮はしていません。
  • chokudai_S001 J - 転倒数:順列をバブルソートしたときの交換回数を求める基本形です。
  • Library Checker - Static Range Inversions Query:区間の転倒数を答えるクエリを処理します。値は 10910^9 までなので座標圧縮が必要です。
  • ABC264 D - “redocta”.swap(i,i+1):各文字を atcoder での位置に置き換えると、順列の転倒数を求める問題になります。
  • ABC190 F - Shift and Inversions:先頭の要素を末尾に移したときの転倒数の変化を考え、すべての巡回シフトの転倒数を求めます。
  • ABC261 F - Sorting Color Balls:全体の転倒数から、同じ色どうしの転倒数を引きます。
  • ARC075 E - Meaningful Mean:累積和に直すと、l<rl < r かつ bl≤brb_l \le b_r となる組を数える問題になり、転倒数と同じく BIT で数えられます。
  • ARC136 B - Triple Shift:操作で転倒数の偶奇が変わらないことを使って判定します。同じ値があるときの扱いがポイントです。
  • ARC120 C - Swaps 2:Ai+iA_i + i に置き換えると隣接交換の問題になり、対応づけた順列の転倒数が答えです。
  • ARC088 E - Papple Sort:各文字の行き先を貪欲に決めたあと、行き先の順列の転倒数を数えます。
  • DOJ Beginner Contest 8 E - Swap Two Elements
    • 1 回の操作で転倒数がちょうど 11 しか変わらないことを示し、答えが転倒数になることをバブルソートで構成しています。
  • AALC001 D - Inversion Count
    • 値が 0,1,20, 1, 2 だけの列で、各値の個数と区間内の転倒数をセグメント木に載せ、1 点更新と区間の転倒数のクエリに答えています。