2006/Contest/国内予選

Problem C: Hexerpents of Hexwamp †

問題概要 †

解法 †

20 歩と聞いてびびってしまいがちだが、よく考えると、大蛇が取りうる状態数はあまり多くないことがわかる。 (*1)

よって、キャッシュをつけた幅優先探索で何とか間に合う。

もっとも、それでも実装はかなり大変だが...。 (三廻部; Jul 3, 2006)

(*1) 問題文より、大蛇の頭が縦に 1 マス移動するのに 4 歩、横に 1 マス移動するのに 2 歩必要。このことから、初期位置から 20 歩以内に大蛇の頭が存在する可能性があるマスの数は 10 * 20 = 200 マス以下。

離れた節が癒着してはならないという条件から、あるマスに大蛇の頭があるとき大蛇が取りうる姿勢のパターンはかなり制限される。頭から 2 番目の節がある位置が 6 通り、それ以降の節が繋がる位置はそれぞれ最大で 3 通りなので、全体では 6 * 3^6 = 4374 通りより少ない。

以上から、大蛇が取りうる状態数は 200 * 4374 = 874800 よりは小さいことが言える。実際には、初期位置から離れるほど大蛇の取る姿勢のパターンが少なくなる／大蛇が取る姿勢は 4374 より更に少ない、などの理由により、もっと小さくなる。 (三廻部; Jul 3, 2006)

議論 †

それでもサンプルを実行するのに数分かかってるけど。工夫次第でもう少し早くなると思います。

実装はちんたらやってたら 1 時間半程度かかってしまいました。 (三廻部; Jul 3, 2006)

ファイルを添付する †

terashima_C.cpp

mikurube_hexerpents.cpp