転倒数・反転数について
- 連続する整数を何回入れ替えると(=バブルソートすると)昇順に並ぶのかをカウントする
- bidを用いたdpのようなことをして計算量を
O(n^2)からO(n log n)にする
基本的な考え方
数字をbitで表現すると大小を少ない回数(ビットのフラグだけ)の操作で、ある値以上、ある値以下の出現回数のdpを作成することができる
kという数字をシフトするのにk + (k & -k)という操作を用いる
具体的な挙動のイメージを掴むのにgoogle colabを用意した
pythonでの実装例1
N = 6
A = [2,1,3,5,4,6]
class BIT:
def __init__(self, N):
self.data = [0]*(N+1)
def add(self, k, x):
data = self.data
while k <= N:
data[k] += x
k += k & -k
def get(self, k):
data = self.data
s = 0
while k:
s += data[k]
k -= k & -k
return s
b = BIT(N=N)
ans = 0
for i, a in enumerate(A):
ans += (N-1-i) - b.get(a)
b.add(a, 1)
print(ans) # 2
pythonでの実装例2
class BIT:
"""
入力されるリストの最小値は1以上である必要がある
"""
def __init__(self, N):
self.data = [0]*(N+1)
self.N = N
def add(self, k, x):
data = self.data
while k <= self.N:
data[k] += x
k += k & -k
def get(self, k):
data = self.data
s = 0
while k:
s += data[k]
k -= k & -k
return s
def get_num(self, arr):
num = 0
for i, a in enumerate(arr):
num += (self.N-1-i) - self.get(a)
self.add(a, 1)
return num
参考
例; バブルソートの操作回数を求める
問題
解答
N = int(input())
*A,=map(int,input().split())
class BIT:
"""
入力されるリストの最小値は1以上である必要がある
"""
def __init__(self, N):
self.data = [0]*(N+1)
self.N = N
def add(self, k, x):
data = self.data
while k <= self.N:
data[k] += x
k += k & -k
def get(self, k):
data = self.data
s = 0
while k:
s += data[k]
k -= k & -k
return s
def get_num(self, arr):
num = 0
for i, a in enumerate(arr):
num += (self.N-1-i) - self.get(a)
self.add(a, 1)
return num
b = BIT(N=N)
print(b.get_num(A))
例; 反転数を普通に求めたあと、リストの操作を一般化する例
問題
解説
- 先頭から要素を削除するコストと、後ろに要素を追加するコストの差を見ることで一般化が可能
解答
N=int(input())
*A,=map(lambda x:int(x)+1, input().split())
class BIT:
def __init__(self, N):
self.data = [0]*(N+1)
def add(self, k, x):
data = self.data
while k <= N:
data[k] += x
k += k & -k
def get(self, k):
data = self.data
s = 0
while k:
s += data[k]
k -= k & -k
return s
b = BIT(N=N)
ans = 0
for i, a in enumerate(A):
# 自分より小さい要素がいくつ存在するかを計算
ans += (N-1-i) - b.get(a)
b.add(a, 1)
for i in range(N):
print(ans)
# 先頭を取り除くことで省略できるコストA[i](左端からみたA[i]まで移動するコスト)
# 末尾に追加するこてで追加されるコストN+1-A[i] (右端からみたA[i]まで移動するコスト)
ans += N+1 - A[i]*2
例; 反転しない例外文字がある文字列の反点数を求める
問題
説明
- 置換を簡単化する; “BC” -> “D”
- 反転しない文字はそこで反転の操作が終了なので、細かく転置数の範囲を分けて累積の転置数をカウントすれば良い
解答
S = input()
"""
1. BCをDに変換する
2. 余ったB,Cは転置数の末端になる
3. 累積の転置数を数えれば良い
"""
S = S.replace("BC", "D")
class BIT:
"""
入力されるリストの最小値は1以上である必要がある
"""
def __init__(self, N):
self.data = [0]*(N+1)
self.N = N
def add(self, k, x):
data = self.data
while k <= self.N:
data[k] += x
k += k & -k
def get(self, k):
data = self.data
s = 0
while k:
s += data[k]
k -= k & -k
return s
def get_num(self, arr):
num = 0
for i, a in enumerate(arr):
num += (self.N-1-i) - self.get(a)
self.add(a, 1)
return num
ans = 0
tmp = []
for i in range(len(S)):
if S[i] in {"B", "C"}:
try:
b = BIT(len(tmp))
ans += b.get_num(tmp)
except:
pass
finally:
tmp = []
elif S[i] == "A":
tmp.append(2)
else:
tmp.append(1)
try:
b = BIT(len(tmp))
ans += b.get_num(tmp)
except:
pass
print(ans)
例; 一見、反転数の適応例に見えるが実は違う例
問題
解説
実は貪欲で解ける問題である
解答