- 考えたこと
- 一般の操作はたくさんあるから、もっと制限したい
- 最適解の中に1を最初に動かすものがあるか
- そうとは限らない
- 最初から1が先頭にある場合
- 1より手前の数値を後ろに動かす場合
- たとえば3,1,2は3を動かせば1回だが、1を先頭に持ってきてもダメ
- 先頭または末尾の値を距離が遠い方から選んでいくのでよいかな？？
- 「先頭または末尾の値を距離が遠い方から選んでいく」について
- 同じ数を2回動かすことはない
- 距離が遠い方の数を動かさないとするなら…
- 3,2,1,6,5,4
- 悪くはならなさそう？もう少し確信が欲しい
- 転倒数を考える
- 端の数が、自分より手前の自分より大きい数を飛び越した数だけ転倒数が減る
- 長さNの列の転倒数は最大で三角数T(N-1)
- うーむ
- 「先頭または末尾の値のうち転倒数が大きい方を端に動かす」が正しい貪欲アルゴリズムであることを示したい
- 動かした後は一回り小さい問題に帰着する
- Nが3の時は正しい
- 手数が転倒数に対して単調非減少であることがそれっぽいけど示せてない
- 制約をもう一度見る
- 30万
- 転倒数の計算ってどうやるんだっけな。
- 公式解説