AGC054 C Roughly Sorted

解くのに恐ろしく時間がかかったので簡単にまとめたい。

最小操作になるにはどうするかにめっちゃ時間がかかった。

まず、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の後ろのほうから並べていけばよい。