概要

与えられた順列に対して、隣り合う要素の入れ替えをちょうど \(K\) 回行った後の「転倒数」の最小値を求める問題です。

考察

まず、転倒数の性質と隣接要素の入れ替え（swap）の関係について考えます。 - 昇順にソートされた状態の転倒数は \(0\) です。 - 隣り合う2要素をswapすると、その2要素の大小関係が逆転するため、転倒数は必ず \(+1\) または \(-1\) されます。

初期状態の転倒数を \(V\) とします。目標は転倒数を最小化することなので、基本的には転倒数を減らす方向（\(-1\) するswap）を選び続けたいです。

ここで、\(K\) 回の操作後に到達可能な転倒数の最小値を場合分けして考えます。

1. \(K \le V\) の場合 \(1\) 回の操作で転倒数を \(1\) 減らすことができるため、\(K\) 回の操作で転倒数を \(K\) 減らすことができます。これ以上減らす必要はなく、ちょうど \(K\) 回で止められるため、最終的な転倒数の最小値は \(V - K\) となります。

2. \(K > V\) の場合 まず \(V\) 回の操作を行うことで、転倒数を \(0\)（完全にソートされた状態）にすることができます。しかし、操作は ちょうど \(K\) 回 行わなければならないため、残りの \(K - V\) 回の操作を行う必要があります。

転倒数が \(0\) の状態で隣接要素をswapすると転倒数は \(1\) になります。さらに、その2要素をもう一度swapして元の状態に戻すと、転倒数は再び \(0\) になります。 つまり、転倒数 \(0\) の状態から \(2\) 回の操作を行うことで、再び転倒数 \(0\) の状態に戻ることができます。

したがって、余った操作回数 \(K - V\) が偶数であれば、転倒数 \(0\) の状態で終わらせることができます。一方、\(K - V\) が奇数の場合は、最後に \(1\) 回余ってしまうため、転倒数 \(1\) の状態で終わるしかありません。 よって、最終的な転倒数の最小値は \((K - V) \bmod 2\) となります。

アルゴリズム

1. 初期状態の転倒数 \(V\) を求める BIT (Binary Indexed Tree) またはセグメントツリーを用いて、\(O(N \log N)\) で転倒数を計算します。 左から順に要素を見ていき、今までに出てきた要素のうち自分より大きいものの個数を足し合わせていくことで転倒数が求まります。

2. 条件分岐による答えの出力

   • \(K \le V\) のとき、答えは \(V - K\)
   • \(K > V\) のとき、答えは \((K - V) \bmod 2\)

計算量

• 時間計算量: \(O(N \log N)\) 転倒数の計算に BIT を用いるため、\(N\) 個の要素に対してそれぞれ \(O(\log N)\) の操作を行います。
• 空間計算量: \(O(N)\) BIT のデータ構造を保持するための配列を使用します。

実装のポイント

• Pythonでは大きな整数も自動で扱えるため問題ありませんが、C++などの言語では \(K\) が最大 \(10^{18}\) になるため、long long 型などの64ビット整数型を使用する必要があります。

• BITの実装では、インデックスが \(1\) から始まることに注意してください。配列のサイズは \(N+2\) 程度確保しておくと安全です。

  ソースコード

import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    P = [int(x) for x in input().split()]
    
    tree = [0] * (N + 2)
    V = 0
    for i in range(N):
        p = P[i]
        
        s = 0
        idx = p
        while idx > 0:
            s += tree[idx]
            idx -= idx & -idx
            
        V += i - s
        
        idx = p
        while idx <= N:
            tree[idx] += 1
            idx += idx & -idx
            
    if K <= V:
        print(V - K)
    else:
        print((K - V) & 1)

if __name__ == '__main__':
    solve()

この解説は or-glm5.2-high によって生成されました。