概要

順列に対して「隣接する2要素の交換」をちょうど \(K\) 回行ったときの、転倒数の最小値を求める問題です。隣接交換が転倒数を \(\pm 1\) だけ変化させる性質を使うと、初期転倒数 \(T\) だけから答えを計算できます。

考察

重要な観察：隣接交換は転倒数を1だけ変える

隣り合う2人 \(P_i\) と \(P_{i+1}\) を交換すると、この2要素以外との位置関係は一切変わりません。変化するのはこの2要素の大小関係だけです。

• \(P_i > P_{i+1}\)（逆順）のとき交換すると、転倒が1つ解消され、転倒数は \(-1\)。
• \(P_i < P_{i+1}\)（正順）のとき交換すると、転倒が1つ増え、転倒数は \(+1\)。

つまり、1回の操作で転倒数はちょうど \(1\) だけ増えるか減るかします。操作のたびに転倒数の偶奇（パリティ）が反転することがポイントです。

操作回数 \(K\) ごとの場合分け

初期の転倒数を \(T\) とします。

ケース1：\(K \le T\) のとき

転倒している箇所を選んで交換すれば、毎回 \(1\) ずつ転倒数を減らせます。\(K\) 回すべてを「減らす操作」に使えるので、到達できる最小値は $\(T - K\)$ となります。

ケース2：\(K > T\) のとき

まず \(T\) 回の操作で転倒数を \(0\)（完全に昇順）にできます。しかし操作は「ちょうど \(K\) 回」行う必要があるため、残り \(K - T\) 回の操作を消化しなければなりません。

転倒数が \(0\) の状態からは、どの隣接交換も必ず転倒数を \(+1\) にします。そこで、適当な2要素を「交換 → 元に戻す」を繰り返すと、転倒数は \(0 \to 1 \to 0 \to 1 \to \cdots\) と振動します。

したがって残り \(K - T\) 回の操作後の転倒数は、その偶奇で決まります。 - \(K - T\) が偶数なら最小値は \(0\) - \(K - T\) が奇数なら最小値は \(1\)

これは \((K - T) \bmod 2\) とまとめられます。

素朴なアプローチの問題点

「実際に操作をシミュレーションする」方法では、\(K\) が最大 \(10^{18}\) にもなるため到底間に合いません。上記の考察により、答えは初期転倒数 \(T\) さえ求めれば \(O(1)\) で確定します。

アルゴリズム

やるべきことは「初期転倒数 \(T\) を求める」ことだけです。転倒数は BIT（Binary Indexed Tree / フェニック木） を使って効率的に数えられます。

具体的な手順（配列を右から左へ走査）： 1. BIT を「これまでに見た値の集合」として管理する。 2. 位置 \(i\) の値 \(v = P_i\) について、すでに右側に現れた値のうち \(v\) より小さいものの個数を query(v-1) で求め、\(T\) に加算する。これは「\(i < j\) かつ \(P_i > P_j\)」となる組のうち \(i\) を固定したときの個数に対応します。 3. update(v) で値 \(v\) を BIT に登録する。

走査が終われば \(T\) が転倒数になります。あとは上記の場合分けで答えを出力します。

計算量

• 時間計算量: \(O(N \log N)\)（BIT による転倒数計算が支配的。場合分けは \(O(1)\)）
• 空間計算量: \(O(N)\)（BIT の配列）

実装のポイント

• \(K\) は最大 \(10^{18}\) と非常に大きいので、言語によっては64bit整数（Pythonでは多倍長整数なので問題なし）を意識する必要があります。

• 値が \(1\) から \(N\) の順列であることを利用し、BIT のインデックスに値そのものを使えます。

• 場合分けは「\(K \le T\) なら \(T - K\)」「それ以外は \((K - T) \bmod 2\)」という非常にシンプルな式に帰着できる点が本問の核心です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    P = [int(input_data[idx + i]) for i in range(N)]
    
    # 転倒数を BIT で計算
    bit = [0] * (N + 1)
    
    def update(i):
        while i <= N:
            bit[i] += 1
            i += i & (-i)
    
    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    T = 0
    # 右から左へ
    for i in range(N - 1, -1, -1):
        v = P[i]
        # v より小さい値で既に右側にあるものの数
        T += query(v - 1)
        update(v)
    
    if K <= T:
        ans = T - K
    else:
        ans = (K - T) % 2
    
    sys.stdout.write(str(ans) + "\n")

main()

---

この解説は claude4.8opus-high によって生成されました。