コンテンツにスキップ

転倒数

タグ「転倒数」の記事 4 件

ABC479 F - Narrow Passage

NN 人が数直線上に立っていて、人 ii ははじめ座標 SiS_i にいます。1 回の操作では、1 人を選んで座標 xx から x−1x - 1 か x+1x + 1 に動かします。移動先に人がいれば、その人は同時に座標 xx に移ります(2 人が入れ替わります)。

すべての人 ii が座標 TiT_i にいる状態にするための操作回数の最小値を求める問題です(1≤N≤2×1051 \le N \le 2 \times 10^5、0≤Si,Ti≤1090 \le S_i, T_i \le 10^9、SiS_i はそれぞれ相異なり、TiT_i もそれぞれ相異なる)。

1 回の操作は、次のどちらかです。

  • 空いている座標への移動:1 人の座標が 11 変わります。人の並び順は変わりません。
  • 隣の人との入れ替え:隣り合う 2 人の並び順が入れ替わります。2 人がいる座標の集合は変わりません。

人の並び順の変化は入れ替えでしか起こらないので、入れ替えの回数は、はじめと最後で前後関係が逆になっている 2 人の組の個数以上必要です。これは、人を SiS_i の小さい順に並べ、それぞれの TT での順位を書いた列の転倒数です。

空いている座標への移動の回数を見積もるため、人 ii について

ui=(人 i の座標)−(人 i より左にいる人数)u_i = (\text{人 } i \text{ の座標}) - (\text{人 } i \text{ より左にいる人数})

を考えます。座標がすべて 00 以上なら、uiu_i は座標 00 から人 ii の手前までにある空いている座標の個数です。

  • 空いている座標へ移動すると、動いた人の uiu_i がちょうど 11 変わり、ほかの人の uu は変わりません。
  • 入れ替えでは、右に動いた人は座標が 11 増えて左にいる人数も 11 増え、左に動いた人はどちらも 11 減るので、2 人とも uu は変わりません。

SS の中で SiS_i より小さいものの個数を rir_i、TT の中で TiT_i より小さいものの個数を ri′r'_i とすると、はじめの uiu_i は Si−riS_i - r_i、最後の uiu_i は Ti−ri′T_i - r'_i です。したがって、空いている座標への移動は少なくとも ∑i∣最後の ui−はじめの ui∣\sum_i |\text{最後の } u_i - \text{はじめの } u_i| 回必要です。

1 回の操作で減らせるのは、転倒数と ∑i∣ui の差∣\sum_i |u_i \text{ の差}| のどちらか一方だけで、それも 11 ずつです。したがって、答えは少なくとも

(転倒数)+∑i∣最後の ui−はじめの ui∣(\text{転倒数}) + \sum_i |\text{最後の } u_i - \text{はじめの } u_i|

です。実はこの回数で必ず達成でき、これが答えになります。現在の状態で、上の値を 11 減らす操作が必ずあることを示します。以下、目標の uiu_i を ui′u'_i と書きます。左から並べたとき uu は広義単調増加で、2 人の uu が等しいのは座標が隣り合っているときです。u′u' も目標の並び順で広義単調増加です。

  • ui<ui′u_i < u'_i の人がいるとき:そのような人のうち最も右にいる人を ii とします。ii の右隣の座標が空いていれば、ii を右に動かすと uiu_i が ui′u'_i に 11 近づきます。右隣に人 jj がいるとき、uj=uiu_j = u_i です。jj は ii より右にいるので uj≥uj′u_j \ge u'_j で、uj′≤uj=ui<ui′u'_j \le u_j = u_i < u'_i です。目標では u′u' が並び順に広義単調増加なので、jj は ii より左に来るはずです。ii と jj を入れ替えると、転倒数が 11 減ります。
  • ui>ui′u_i > u'_i の人だけがいるとき:左右を逆にして同様です。
  • すべての人で ui=ui′u_i = u'_i のとき:転倒数が正なら、目標と前後が逆の隣り合う 2 人 ii(左)、jj(右)がいます。ui≤uju_i \le u_j かつ uj′≤ui′u'_j \le u'_i なので ui=uju_i = u_j となり、2 人は座標が隣り合っています。入れ替えれば転倒数が 11 減ります。

SS と TT をそれぞれソートして順位を求め、転倒数を BIT などで数えれば、計算量は O(Nlog⁡N)O(N \log N) です。

Python
N = int(input())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
os = sorted(range(N), key=S.__getitem__)
ot = sorted(range(N), key=T.__getitem__)
rs = [0] * N
rt = [0] * N
for k in range(N):
rs[os[k]] = k
rt[ot[k]] = k
ans = 0
bit = [0] * (N + 1)
for k, i in enumerate(os):
x = rt[i] + 1
c = 0
while x > 0:
c += bit[x]
x -= x & -x
ans += k - c
x = rt[i] + 1
while x <= N:
bit[x] += 1
x += x & -x
for i in range(N):
ans += abs((T[i] - rt[i]) - (S[i] - rs[i]))
print(ans)

os は人を SiS_i の小さい順に並べたもので、rs[i] は人 ii の SS での順位(0 始まり)、つまり SiS_i より小さい SS の個数です。rt も同様に TT での順位です。

転倒数は、os の順に人を見ながら、それまでに見た人のうち TT での順位が人 ii より小さい人数 c を BIT で数え、k - c(順位が大きい人数)を足して求めています。最後に ∣ui′−ui∣|u'_i - u_i| を足しています。

C++
#include "shogo-library/base/all"
#include "shogo-library/others/inversion-number.hpp"
#include "shogo-library/utility/vector_func.hpp"
void solve() {
LL(N);
VL(S, N);
VL(T, N);
vl rs = rank(S), rt = rank(T);
ll ans = inversion_number(select(rt, argsort(S)));
rep(i, N) ans += abs((T[i] - rt[i]) - (S[i] - rs[i]));
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

rank(S) は各要素の SS での順位(0 始まり)、argsort(S) は SS の小さい順に並べた添字の列です。select(rt, argsort(S)) で、人を SS の小さい順に並べたときの TT での順位の列を作り、inversion_number でその転倒数を求めています。inversion_number はマージソートで転倒数を数えます。

使用ライブラリ:cpp_include@6519da7

転倒数のリンク集

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

数列 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 点更新と区間の転倒数のクエリに答えています。

AALC001 D - Inversion Count

0,1,20, 1, 2 からなる長さ NN の数列 AA に対して、次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:(Al,…,Ar)(A_l, \dots, A_r) の転倒数を出力する。

セグメント木の各ノードに、担当区間について次の値を持たせます。

  • cntv\mathrm{cnt}_v:値 vv(v=0,1,2v = 0, 1, 2)の個数
  • inv\mathrm{inv}:区間内の転倒数

隣り合う区間 XX(左)と YY(右)をつなげたときの転倒数は、「XX の中の転倒数」「YY の中の転倒数」「XX と YY にまたがる転倒数」の和です。またがる転倒は、XX の値 ii と YY の値 jj で i>ji > j となる組なので、その個数は ∑i>jcntiX cntjY\sum_{i > j} \mathrm{cnt}^X_i \, \mathrm{cnt}^Y_j です。

invXY=invX+invY+∑i>jcntiX cntjY\mathrm{inv}^{XY} = \mathrm{inv}^X + \mathrm{inv}^Y + \sum_{i > j} \mathrm{cnt}^X_i \, \mathrm{cnt}^Y_j

これで 2 つの区間の情報を O(1)O(1) で合成できるので、セグメント木に載せられます。全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
struct AALC0001D {
struct S {
al<3> cnt;
ll inv;
S() : cnt{}, inv{} {}
S(ll x) : cnt{}, inv{} {
assert(0 <= x && x < 3);
cnt[x] = 1;
}
};
static S op(const S &a, const S &b) {
S res;
res.inv = a.inv + b.inv;
rep(i, 3) {
res.cnt[i] = a.cnt[i] + b.cnt[i];
rep(j, i) {
res.inv += a.cnt[i] * b.cnt[j];
}
}
return res;
}
static S e() { return S(); }
};
void solve() {
LL(N, Q);
VL(A, N);
vec<AALC0001D::S> init;
init.reserve(N);
for (ll a : A)
init.push_back(a);
SegTree<AALC0001D> seg(init);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, x);
seg.set(i - 1, x);
} else if (q == 2) {
LL(l, r);
print(seg.prod(l - 1, r).inv);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SegTree には、要素の型 S、演算 op、単位元 e をまとめた構造体を渡します。al<3> は std::array<ll, 3> です。

使用ライブラリ:cpp_include@402f0cf

DOJ Beginner Contest 8 E - Swap Two Elements

長さ NN の順列 AA が与えられます。次の操作を何回でも行えます。

  • 1≤i<j≤N1 \le i < j \le N を選ぶ。Ai,Ai+1,…,AjA_i, A_{i+1}, \dots, A_j のうち最小の要素と 2 番目に小さい要素の位置を入れ替える。

AA を昇順にするための操作回数の最小値と、その回数を達成する操作の列を 1 つ出力する問題です。NN の総和は 10001000 以下です。

答えは AA の転倒数(位置が前なのに値が大きい組 (p,q)(p, q) の個数)です。

1 回の操作で転倒数は 1 しか変わらない

Section titled “1 回の操作で転倒数は 1 しか変わらない”

区間 [i,j][i, j] で入れ替える 2 つの値を x<yx < y、その位置を p<qp < q とします。

  • 区間内の pp と qq の間にある要素は、どれも xx と yy より大きいです(x,yx, y が区間で最も小さい 2 つだからです)。pp と qq の間にある要素から見ると、xx と yy はどちらも自分より小さいままです。そのため、この要素が関わる転倒の数は、入れ替えても変わりません。
  • pp より前、qq より後ろの要素から見ても、xx と yy の両方が同じ側にあることは変わらないので、転倒の数は変わりません。

変わるのは xx と yy の組だけで、転倒数はちょうど 11 増えるか 11 減ります。昇順の順列の転倒数は 00 なので、操作は転倒数の回数以上必要です。

隣どうしの入れ替えで達成できる

Section titled “隣どうしの入れ替えで達成できる”

j=i+1j = i + 1 とすると、区間は Ai,Ai+1A_i, A_{i+1} の 2 つだけなので、この操作は隣どうしの入れ替えです。バブルソートのように、Ai>Ai+1A_i > A_{i+1} となっている隣の組を入れ替えるたびに、転倒数は 11 ずつ減ります。したがって、ちょうど転倒数の回数で昇順にできます。

NN の総和が 10001000 以下なので、O(N2)O(N^2) のバブルソートで十分間に合います。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = []
for _ in range(N):
for i in range(1, N):
if A[i - 1] > A[i]:
ans.append((i - 1, i))
A[i - 1], A[i] = A[i], A[i - 1]
print(len(ans))
for x, y in ans:
print(x + 1, y + 1)

バブルソートを行い、入れ替えた隣の組 (i,i+1)(i, i+1) を記録して出力しています。