AtCoder ABC224
ABC224参加しました。
今回もC,D問題だけ。
C - Triangle?
解説 - AtCoder Beginner Contest 224
提出 #26766378 - AtCoder Beginner Contest 224
ベクトルの外積の性質を考えればすぐに解けます。
for文で全探索すると、$ O(N^{3}) $の計算量ですが、頂点数が少ないので、間に合います。
D - 8 Puzzle on Graph
解説 - AtCoder Beginner Contest 224
提出 #26784267 - AtCoder Beginner Contest 224
一般化したスライドパズルと言えそうです。
実際、コンテスト中に以下のようなページを見つけて使えそうだなとは思いました。
なので、あまり書くこともないですが...
スライドパズルの各盤面を頂点として持つグラフを考えます。盤面は解説にある通り文字列として持ってもいいです。入力例1だと、頂点"931456782"からスタートして、"123456789"(ゴールの頂点)への最短経路を探ります。
BFSでの迷路の最短経路探索では、一度通ったマスには通らないようにしないといけません。私の提出したプログラムでは、通ったマスは全部マスのハッシュ値(といっても頂点の数値をそのままintにしたもの)を覚えておいて、それと一致するかを見ています。 HashSet検索なので、検索コストも速いはず。
0-indexedか1-indexedか、ちょっとややこしいです。
最大でも数字の並びは9! = 362880 なので $3 \times 10^{5}$程度のノード数しかないです。
感想
スライドパズルの解法がそのまま使えそうだったのは面白かった。なお、問題では頂点数が最大で9の9スライドパズルでしたが、15スライドパズルになると、頂点数が最大で16! = 20922789888000で頂点数が膨大になり、ナイーブなBFSでは扱えなくなるそうです。調べたところ、こういうスライドパズルでは、A*などのヒューリスティックな探索を用いるとのこと。
