- 考えたこと
- N回あれば十分
- 同じものを2回動かすことはない
- 2回目だけやっても結果が同じだから
- 2回やっても意味がない
- というわけで与えられたものに対して「先頭に動かす」「末尾に動かす」「動かさない」の3つに分ける問題
- 動かさなかったものが昇順になる必要がある
- 「数の小さい方からa個、大きい方からb個を消した時に残りが昇順であるようなa,bのうち和が最小のものを探せ」という問題
- 素朴に探すと二乗のオーダー
- 逆に「昇順であるような列」の最も長いものを探す
- 線形オーダーで「数→位置」を作る
- 数を小さい方から見ていって位置が増加している間カウント、減少したらリセット、一番大きなカウントになる場所を見つける
- これは線形オーダー
- 公式解説
- OK