解くのに恐ろしく時間がかかったので簡単にまとめたい。
最小操作になるにはどうするかにめっちゃ時間がかかった。
まず、P[j]>P[i]となっているjの個数がKより大きくなっているところを見ると1回のswapでどこかのiについて-1しかできないから、xを個数とすると理想的な最短はΣ(x-K)となる。また、そのような場所のもっともindが小さいところを見ると必ずP[i-1]>P[i]が成り立つ。よって、indが小さい場所から条件を達成していけばよいことがわかる。
また操作が完了すると、x=Kとなっているところの間は必ず昇順になっていることも分かる。
よって
B1 A1,B2, A2,B3,B4 A3,A4 B5,B6 A5
B:x<K
A:x=Kとする。すると各Biは、前のAjよりも大きい値でなければならない。
これを踏まえると、最短操作は前から順に自分よりも大きい値がKより大きかったら
x-K回そこでswapする、を繰り返すことである。
そうすると、与えられたP’からPを作る操作は、後ろのAから順に
Aiより後ろにある値について、好きなだけ前にもっていく、ことを繰り返すということである。
Bの順は不変で、Aは Aiの前にあるBjより後ろの条件を満たすように配置すればよく、Aの後ろのほうから並べていけばよい。