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)


ファイルを添付する

fileterashima_C.cpp 989件 [詳細] filemikurube_hexerpents.cpp 1376件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: fileterashima_C.cpp 989件 [詳細] filemikurube_hexerpents.cpp 1376件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:38 (4575d)