E - 整列の手間 / The Effort of Sorting 解説
by 
MMNMM
隣接する \(2\) 要素 \(P _ i,P _ {i+1}\) を入れ替えたとき、転倒数がどのように変化するかについて考えます。
\(P _ i,P _ {i+1}\) のどちらでもない要素が含まれるペアについては、添え字と値の大小関係は操作の前後で変化しません（ここで、添え字ではなく列の値で組を見ていることに注意してください。たとえば、操作前の組 \((k,i)\) には操作後の組 \((k,i+1)\) を対応させています）。 よって、\(P _ i\lt P _ {i+1}\) なら、操作の前後で転倒数は \(1\) 増加します。\(P _ i\gt P _ {i+1}\) なら、操作の前後で転倒数は \(1\) 減少します。
すべての組が \(P _ i\lt P _ {i+1}\) を満たすとき、かつそのときに限り転倒数は \(0\) です。 同様に、すべての組が \(P _ i\gt P _ {i+1}\) を満たすとき、かつそのときに限り転倒数は \(\dfrac{N(N-1)}2\) です。
これらの事実から、はじめの転倒数が \(I\) の状態からちょうど \(K\) 回操作を行ったときの転倒数 \(J\) は次の条件を満たすことがわかります。
- \(0\le J\le\dfrac{N(N-1)}2\)
- \(I-K\le J\le I+K\)
- \(I+K\equiv J\pmod 2\)
逆に、これらの条件を満たす \(J\) について、ちょうど \(K\) 回の操作で転倒数を \(J\) にできることもわかります。
証明
次のような手順を考えます。
- 現在の転倒数が \(J\) より大きいなら、\(P _ i\lt P _ {i+1}\) なる組に対して操作を行う。
- 現在の転倒数が \(J\) より小さいなら、\(P _ i\gt P _ {i+1}\) なる組に対して操作を行う。
- 現在の転倒数が \(J\) なら、適当な組に対して操作を行う。
一番目の条件から、上の手順が常に行えることがわかります。
この手順を行ったとき、はじめて \(J\) に到達するまでに \(|I-J|\) 回の操作を行います。 二番目の条件から、\(K\) 回操作を行うまでに \(J\) に到達することがわかります。
一度 \(J\) に到達したら、そのあとの転倒数 \(x\) は \(|x-J|\le 1\) を満たします。 三番目の条件から、ちょうど \(K\) 回の操作を行ったあとの転倒数 \(x\) の偶奇は \(J\) と等しいので、\(x=J\) が示されました。
よって、上の条件を満たす \(J\) の最小値を求めればよいです。
\(0,1,I-K\) のいずれかが求める最小値となるので、それらを全部試せばこの問題を解くことができます。
はじめの転倒数 \(I\) を求めるのがボトルネックとなり、時間計算量は \(O(N\log N)\) などとなります。
実装例は以下のようになります。
#include <iostream>
#include <atcoder/fenwicktree>
using namespace std;
int main() {
int N;
long K;
cin >> N >> K;
# 転倒数を求める
atcoder::fenwick_tree<int> bit(N);
long inversion = 0;
for (int i = 0; i < N; ++i) {
int A;
cin >> A;
inversion += bit.sum(A, N);
bit.add(A - 1, 1);
}
if (inversion >= K) {
cout << inversion - K << endl;
} else {
cout << (inversion + K) % 2 << endl;
}
return 0;
}
from atcoder.fenwicktree import FenwickTree
N, K = map(int, input().split())
# 転倒数を求める
bit = FenwickTree(N)
inversion = 0
for A in map(int, input().split()):
inversion += bit.sum(A, N)
bit.add(A - 1,1)
if inversion >= K:
print(inversion - K)
else:
print((inversion + K) % 2)
投稿日時:
最終更新: