第三回日本最強プログラマー学生選手権-予選- (AtCoder Beginner Contest 262) F - Erase and Rotate (500)
$ k=0の場合、操作できないのでそのまま出力
前$ k個と後ろ$ k-1個の中から最小値の位置を求めておく
最小値が前半にある場合、
最小値の前までの要素は削除
残りの要素については以下を行う
削除がもうできない場合何もしない
後ろの要素を全て削除できるなら全て削除
現在地点と現在地点から貪欲に削除していった場合に最初の要素になる地点の間で現在地点の値が最小値でないなら削除する
削除を行った後の完成した配列が最小値の配列を更新していれば更新
最小値が後半にある場合、
先頭から残りの操作可能な範囲の中で最小値を求めておく
最小値の地点から末尾までについて後ろから見る
最小値を更新するなら先頭に移動する
最小値を更新しないなら削除する
最小値を更新するということはこれ以前の要素を固定したときにこの要素が有った方が辞書順で小さくなる
どちらの操作を選んでも全体の操作回数に影響は無い
移動前の先頭から最小値の部分までについては最小値が前半の場合の残りの要素の処理と同じ
ついでに$ n-k以下の値だけを取った配列も作っておき最小値を更新するか確認する