JAG 2015 Summer Day2 K Leapfrog - ヘクトのメモ

3ヶ月越しのFirstAccepted
ネタバレ注意

K: Leapfrog - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder

問題概要

N個のマスが円状に並んでいて,M個の駒が最初 $x_1,x_2,...,x_M$ と並んでいる．
駒の移動は隣にある駒を飛び越して空きマスへの移動のみ可能
最終的に,M個の駒を $y_1,y_2,...,y_M$ に移動させることが可能かどうか?
駒を最小何回動かせ

夏合宿で聞いたヒント

駒空逆

解法

まず，隣り合う駒の組が存在するかを調べる．
存在しない場合は駒の移動はできない，
この場合は初期状態と終了状態が一致するかを調べる．一致すれば0,そうでなければ-1

以下では駒の移動はできると仮定する．
ここで駒と空きマスの関係を逆にして考える．
駒をo,空きマスをxで表す．

例えば,サンプル1 の初期状態について考える．
ooxxxxx
1番目のマスにある駒を3番目のマスに移動させる．
xooxxxx
このとき，3番目のマスにある空きを1番目のマスに移動させたと解釈ができる．

つまり，駒の移動を空きマスの移動と考えると以下の2つの操作は同じと解釈できる．
駒の移動は,隣にある駒を飛び越して空きマスへの移動
空きマスは,駒のあるマスを辿って2マス移動

そこで，初期状態の空きマスが終了状態のどの空きマスの対応するかを全探索する．
空きマスの移動方向について時計回りと反時計回りの2パターン試す．
そうすると,残りの空きマスの位置関係が決まるので計算する．
実装では,空きマスの差分を持つと楽?
ただし,M=N-1の時に場合分けが必要．
計算量は $O(n^2)$

ソースコード
 Submission #601386 - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder