SRM425 Level2 PiecesMover

コンテスト中に書いたコードは、時間がかかる入力が来ると結果が出るまでに20秒以上かかってました。
この程度の遅さなら、アルゴリズムのオーダーが悪いのではなくて定数項の違いだろうと思い、ちょっと書き直し（オーダーが間違ってたら、遅いケースでは何十分もかかることが多い）。

5×5の盤面のマスに左上から順に0〜24まで番号を付けて、どこにコマが置いてあるかの状態を管理するんですが、初めのコードでは状態を HashSet で持ってました。
これを、Setじゃなくて1つのint変数内部のビットフィールドで表すように変更。

すると100倍くらい高速化されて、あっさりシステムテスト通ってしまった。うおーそんなに違うのかー。Setってここまで遅いんだ。

できる限りコレクションは使わずにプリミティブのまま扱った方がいいんでしょうな。
これまではとにかく、計算量のオーダーだけを考慮してアルゴリズムを考えていたんですが、それだけじゃ不十分なこともあるんですね。オーダー違いじゃなくて定数部分で通らなかったというのは初めてだったので、教訓になりました。