はじめに

本解説では \(2\) つの操作のうち前者を削除、後者を回転と呼ぶことにします。
本問では操作を \(0\) 回以上 \(K\) 回以下行えることになっていますが、操作回数が増えると辞書順でより小さな列を得られるため、実際はちょうど \(K\) 回操作を行うことになります。具体的には、\(K\) 回未満の操作で列を得た場合は余った操作で末尾の項を削除することでより辞書順で小さな列を得られます。

回転を行わない場合

まず、削除のみを \(0\) 回以上 \(K\) 回以下行って得られる辞書順最小の \(P\) を考えます。操作後の \(P\) の先頭の項として考えられるのは、\(p_1,p_2,\ldots,p_{K+1}\) のどれかです。(操作は \(K\) 回までしか行えないため、\(p_{K+2}\) 及びそれ以降の項は先頭の項になりません) 辞書順に基づいた比較がまず先頭の項の大小で行われることを考えると、先頭の項として選ばれるべきはこれらのうち最小の値です。\(2\) 項目以降も同様にして最小のものを貪欲に選ぶことになります。
このシミュレーションを愚直に行うと、最大 \(N\) 個程度の値のうち最小値を調べる処理を最大で \(N\) 回程度行うため \(\mathrm O (N^2)\) となり、実行時間制限に間に合いません。そこで、Segment Treeを用いる等の高速化を行う必要があります。

回転を \(1\) 回以上行う場合

まず、いくつかの性質を示します。

• 回転によって移動した項を削除するのは無駄です。なぜなら、移動を行う前にその項を削除すれば \(1\) 回の操作で同じ結果が得られるためです。
• 削除・回転は任意の順番で行うことが出来ますが、これをによって得られる \(P\) のうち辞書順最小のものは以下の操作順で再現できます。
  • まず回転を \(0\) 回以上行う。
  • 続いて削除を \(0\) 回以上行う。ただし、先の回転によって先頭に移動した項の削除は操作の回数に数えない。(回転の代わりに削除したものとみなす)

\(2\) 番目の性質より、回転を \(1,\ldots,K\) 回行った場合それぞれについて回転を行わない場合と同様のシミュレーションを行って得られるもののうち辞書順最小のものを答えれば正答が得られますが、時間計算量が \(\mathrm O(N^2 \log N)\) となってしまいます。そこで、\(1\) 番目の性質を考えると回転を \(1\) 回以上行った場合は先頭の項を削除することはないと言え、回転を \(1,\ldots,K\) 回行った場合のうち先頭の項が最小になるもの以外は調べる必要が無いと分かります。よって、この場合と前述の回転を行わない場合の \(2\) つに対してシミュレーションを行い、辞書順で小さい方を出力すれば良いです。

余談

シミュレーション部分はSegment Treeを用いると \(\mathrm O(N \log N)\) となりますが、区間の左端・右端の位置に単調性があるためスライド最小値を用いて \(\mathrm O(N)\) に改善できます。