ACM-ICPC 2010 アジア地区予選 1/3

Javaチャレンジ

トロンはいいとして、アレをパックマンだと主張するくらいならもうちょっと適切な引用元があったと思うな！


以下は、我々のチームのアルゴリズム。
簡単な実装で、目先の一手しか読まずにどこまでそれっぽい動きができるかを目指したとか目指してないとか。




（０）まずは、直進、右折、左折、３通りの動きの候補を持った状態からスタート。
（１）もしある移動をしたら即壁にぶつかってしまう場合、その方向を除外。
（２）もしある移動をしたら、「自分のいる島のマス数　≦　2/3×残りターン数」になってしまう場合、その方向を除外。（もし全方向が除外されてしまったら、あらためて一番大きい島を確保できる方向を候補とする）
（３）自分のいる島に取れるコインが残っている場合、（４）でコインを取りに行く。そうでなければ（５）（６）で長生きを目指す。
（４）全コインを始点とした幅優先探索をして、最も近いコインとの距離が小さくなるように動く。複数通りの候補があれば、最も相手から遠ざかるように動く。
（５）自分の左右どちらか少なくとも一方に壁（or相手の軌跡or自分の軌跡）があるようにできるなら、そのように動く。複数通りの候補がある場合は、一番大きい島を確保できる方向へ行く。
（６）できなければ、右折・左折を優先。それらが既に除外されているならば直進を選択する。




真面目に組んだものには決して勝てないけれど、こんな適当なアルゴリズムにしては意外とよく動く印象。