数列のソート 5

初期整列度を $S$、厳密な逆転数を $D$ とする。隣接する逆転の交換で整列度は $1$ 増える。$K\leq D$ なら挿入ソートの交換を $K$ 回行い $S+K$ を達成する。それ以外ではまず整列する。重複があれば隣接する等しい要素を残り回数だけ交換する。すべて異なる場合は同じ位置を $2$ 回ずつ交換し、残りが奇数なら整列度を $1$ 失う。この損失は順列の偶奇性から避けられない。

時間は $O(N^2+K)$、整列度は高々 $499500$。小さいサブタスクでは各交換の整列度更新を $O(1)$ にして操作列を全探索できる。検査器は有効な添字をちょうど $K$ 個要求し、最大値は正しいが操作列が最適でない場合だけ を与える。