問題の特徴

今回の問題は、複数のカメと複数のエサがあり、取る順番や役割分担を効率化する問題でした。

問題の制作過程では、カメが別のカメの背中に乗り降りするのにも1ターンかかる(乗られるカメは動いてはいけない)など、複雑なルールの問題案も検討しましたが、最終的には、同じ場所にカメが集まるだけで自動的に背中に乗れて高い場所にあるエサが取れるというシンプルなルールに落ち着きました。

また、当初はエサの高さを生成する乱数は一様乱数のみにする方向で検討していましたが、それだとカメがあまり散らばらずにほぼ集団で行動してしまうため、解法のバリエーションを増やすために、低いエサが多いステージ、中くらいのステージを追加してみました。

シンプルですが、考えることが多く、奥が深い問題になったと思います。

作品の傾向

この問題では、どのカメがエサを食べるか、そしてどういう順番で食べるかと、考えることが多くあります。

そこで、まず全体での食べる順番を考え、その上で担当するカメを割り当てるという方が多かったようです。

食べる順番の決め方の1つとして、あらかじめ決められたコースの中から、もっとも良かったものを採用するという方法がありました。

そして、そのコースも、左から右、右から左のほか、時計回り、反時計回り、クネクネとS字を描くように食べるなど、ユニークな手法が見られました。

ほかには、高いエサを食べる順番は巡回セールスマン問題を解いて決めて、低いエサを途中に挟むような手法も見られました。

どのカメが食べるか

ここは単純に、各カメの現在位置と時刻から、早く次のエサに到達できるカメを割り当てるというシンプルな手法が多かったようです。

先ほどは分かりやすく「食べる順番」としましたが、ここでは、「食べるカメを決める順番」とします。この違いについて詳しく説明します。

たとえば、上の図のようなケースで、食べるカメを決める順番がA→B→Cのとき、最初にAを6匹で食べ、そのうちの3匹がBに向かいます。そして、Cを食べるカメを決めるのですが、最も早く到達できるのは、Aに残っている3匹なので、この3匹がCに向かいます。

これを時系列で考えると、Aを6匹で食べた後、Cを3匹で食べ、残りの3匹も同時にAを出発するのですが、実際にはCより後でBを食べるというふうになります。

このように、食べるカメを決める順番と、実際に食べる順番は異なることがあります。

上の図のようなケースでは、食べるカメを決める順番をA→B→C→D→Eとすると、Aを6匹で食べ、そのうちの3匹がBを、残りの3匹がCを食べるようになってしまいます。そして、Bを食べた3匹がDを、Cを食べた3匹がEを食べるようになるのですが、あまり良い戦略とはいえません。

おそらくこの図を見た多くの方は、Aを6匹で食べた後、左右二手に分かれて、左側担当になった3匹はB、Cを、右側担当になった3匹はD、Eを食べるのが良いと考えるのではないでしょうか？　もちろん、それが正解です。

ここで、食べるカメを決める順番を、A→B→D→C→Eとしてみましょう。すると、Aを6匹で食べ、そのうちの3匹がBを、残りの3匹がDを食べます。そして、Bを食べた3匹がCを、Dを食べた3匹がEを食べるようになり、期待通りになります。

このように、食べるカメを決める順番をうまく設定すると、食べるカメの決め方はシンプルでも、それなりにうまく分業するようになるため、とにかく食べるカメを決める順番をいろいろ試してみるという方が多かったようです。

そして、ここでの適切な食べるカメを決める順番は、もはや巡回セールスマン問題を解いて求めたようなものとは違います。ビームサーチや焼きなまし法などでこれを改善する方が多かったようです。

評価環境

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

でした。