SRM397 Div2 500

問題

このソーティングゲームでは、1からnまでの数字を含む数列が与えられ、1回の移動で連続したk個の要素を逆順にすることができる。このゲームのゴールは昇順に並んだ数列を作ることで、そのときの最小移動回数を返す。もし不可能ならば-1を返す。

考え方

メモ化bfs。
数列とそれまでの移動回数を状態に持って、k個分逆順にした状態を次の状態にしてキューに入れる。
同じ状態が何度もでてくるのでmap,int>とかメモする。
逆順に並び替えるのはreverse(v.begin()+i, v.begin()+i+k)で配列の一部分だけ逆順にできる。