http://yukicoder.me/problems/247
この問題はシミュレーションとなっていますが、シミュレーションは必要ではないです。
- まず、各駒について、完成状態とのマンハッタン距離を取ります。1つでも2以上であれば、その配置は作ることができません。
- 次に、その盤面が15パズルの盤面として正しいかを確認します。これは、(空マス以外の転倒数+空マスの上下動数)%2が偶数であれば正しいということが言えます。転倒数については
- https://ja.wikipedia.org/wiki/%E8%BB%A2%E5%80%92_(%E6%95%B0%E5%AD%A6)
を参照して下さい。
これらの2条件がそろうとき、問題の配置は正しいと言えます。
- 今回は転倒数の計算はO(nlogn)ではなくO(n2)でよいので、2重ループを書けばよいです。さらに、入力を読み込む途中に適宜転倒数の計算を行うとループの記述が1個消えます。これをまとめると以下のようになります(暫定最短コードです)。