AGC024B

https://gyazo.com/c45a7bf6e5e9f8696fb1c193eb80eaa5

考えたこと

N回あれば十分

同じものを2回動かすことはない

2回目だけやっても結果が同じだから

というわけで与えられたものに対して「先頭に動かす」「末尾に動かす」「動かさない」の3つに分ける問題

動かさなかったものが昇順になる必要がある

「数の小さい方からa個、大きい方からb個を消した時に残りが昇順であるようなa,bのうち和が最小のものを探せ」という問題

素朴に探すと二乗のオーダー

逆に「昇順であるような列」の最も長いものを探す

線形オーダーで「数→位置」を作る

数を小さい方から見ていって位置が増加している間カウント、減少したらリセット、一番大きなカウントになる場所を見つける

これは線形オーダー

公式解説

OK