SRM251 DIV1

500
実はそんなに状態数が多くなく、とりあえず全探索を書いてやらしい入力作ったら通ったのでそのまま提出。本番だったらメモ探組の人から沢山チャレンジ受けてうはうは状態になってそうだった。

1000
id:awakia-nの解法。Aさんのがn個あったとし、それぞれp1,p2,...,pnに置いてあるとする。そうすると例の距離関数の値は(p2-p1)+(p3-p2)+...+(pn-p(n-1))=pn-p1。な、なんだってー。そう、実は両端以外はどういう置き方されてもおｋ。次にA,B,...,Zが同じ順番で両端におかれているとする。どうやって置くと一番良いんだろうか。試しに隣接する要素を一組だけswapしてみる。そうすると片方の距離が1減って、もう片方が1増える。隣接要素のswapだけで順列を生成することが可能なので、いかなる並べ方をしても評価値は変わらないと言うことになる。そしたら言われた通り両端を辞書順に並べる。真ん中はどんな順番でも良いことが保証されているので、真ん中も辞書順に並べる。終了。