abc006_4

https://gyazo.com/dfa52aab4ec8fdab70ef8840ca4370c7

考えたこと

一般の操作はたくさんあるから、もっと制限したい

最適解の中に1を最初に動かすものがあるか

そうとは限らない

最初から1が先頭にある場合

1より手前の数値を後ろに動かす場合

たとえば3,1,2は3を動かせば1回だが、1を先頭に持ってきてもダメ

先頭または末尾の値を距離が遠い方から選んでいくのでよいかな？？

「先頭または末尾の値を距離が遠い方から選んでいく」について

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

距離が遠い方の数を動かさないとするなら…

3,2,1,6,5,4

悪くはならなさそう？もう少し確信が欲しい

端の数が、自分より手前の自分より大きい数を飛び越した数だけ転倒数が減る

長さNの列の転倒数は最大で三角数T(N-1)

うーむ

「先頭または末尾の値のうち転倒数が大きい方を端に動かす」が正しい貪欲アルゴリズムであることを示したい

動かした後は一回り小さい問題に帰着する

Nが3の時は正しい

手数が転倒数に対して単調非減少であることがそれっぽいけど示せてない

制約をもう一度見る

30万

転倒数の計算ってどうやるんだっけな。

公式解説

その場合、うまくいく条件は「抜いた残りの列が単調増加」