結果発表

今回の問題は、複数の巻物と地形によるジャンプ移動可能距離の変化があり、取る順番やコース取りを効率化する問題でした。

今回の問題の一番初めのモチーフはゴルフで、ただ1つのゴールを目指すだけの問題でした。

その後、ゴールを複数個に増やすことを検討し、それが巻物を集めるというルールになりました。

問題の制作過程では、一時的なジャンプ力向上アイテムの導入やウサギの数を増やすといった複雑なルールの追加も検討しましたが、最終的には巻物を取ることでのジャンプ力向上のルールだけを追加することで、シンプルでルールが理解しやすい問題になりました。

理解しやすいルールでありながら工夫の余地がたくさんある、奥深い問題になったのではないかと思います。

この問題では、どの順番で巻物を取るのか、そして地形を考慮してどのようなコースで移動するのかと考えることが多くあります。

そこでまずは、ウサギと巻物、巻物と巻物の間の移動経路を求めて、その上で巻物を取る順番を決定するという方が多かったようです。

今回の問題では、地形によるジャンプ移動可能距離の変化があるため、ただまっすぐ次の巻物を目指すだけでは最適な移動経路にはなりません。「プロコン速報 vol.2」でも触れたように「平地」でのジャンプ移動可能距離は「池」の10倍です。まわり道をしてでも平地を進んでいくほうが早くなる場合があります。「砂地」や「茂み」についても同様です。また、READMEに記載している通り、ウサギは巻物と同じマスに着地することで巻物を取ることができます。そのため、マス目の中心まで移動する必要はなく、マスの端っこをかすめていくように進むことでターン数を短縮することができるかもしれません。

高得点を出している作品では「巻物だけでなく、地形と地形の切り替わるポイントを経由点として探索に組み込む」、「次の一歩を大きく踏み出すために、地形の切り替わるポイントで一度着地する」、「できるだけターン数を短縮できるように探索結果を補正する」などの工夫が見られました。

そうして求めた移動経路を使うと、巻物を取る順番は巡回セールスマン問題に帰着します。

巻物の数は最大20個ですので、全探索するとステージによっては制限時間を超えてしまうかもしれません。したがって、一度調べたものは計算結果を保存しておき、再利用できるようにしておくといった高速化が必要です。このような高速化の手法を一般に「動的計画法（DP）」といい、特に状態をビットで表現する手法を「BitDP」と呼びます。そのほか、参加者の中では「2-opt」や「焼きなまし法」などの手法を取っている方もいたようです。興味のある方は調べてみてください。

評価環境で使われた乱数は、

• randomSeedX = 0x6bba8a51;
• randomSeedY = 0xb4dca512;
• randomSeedZ = 0x728bd6aa;
• randomSeedW = 0x959df8b4;
• randomSpinX = 0x81b;
• randomSpinY = 0xcf;

でした。

今年のプロコンは、開始当初よりかなりの数のご応募があり、例年よりも早いタイミングでランキングの「総ターン数」と「時間（秒）」を公開しました。週末を迎えるたびに応募数が増え、参加者同士で切磋琢磨している様子を見ることができました。

スコアの推移を見ていますと、今回の問題では一定のスコアごとに壁があるように思いました。壁を1つ乗り越えるたび、手ごたえを感じていただけたのではないかと思います。

参加者の声や作品のコメントからは、できることの多さや制限時間に悩まされながらも、初参加の方から常連の方まで各々のスキルに応じて取り組んでいただけたことが伺え、実行委員会としては大変うれしい限りでした。

最後になりますが、プロコン2020はお楽しみいただけましたでしょうか。

このようにプロコンが盛り上がりましたのは参加者のみなさんのおかげと、実行委員会一同、感謝しております。熱心にご応募いただき、本当にありがとうございました。