方針

えさを食べる順番を決定し、近いカメから貪欲に向かわせることにしました。

ビームサーチの亜種であるChokudaiSearchでカメの動きの流れを作ってから、山登り法で細かい調整をしました。

ChokudaiSearchに10秒、山登り法に45秒。

ChokudaiSearchだけで、約56000ターン。そこから山登り法で約52000ターンになりました。

ChokudaiSearch

盤面の評価

• まだ食べてない餌をすべて含む長方形面積の小ささ
• 序盤にカメが近くに集まっていたほうが良い
• まだ食べてない餌を近いところからめぐる距離の小ささ

餌の評価

• ターン数
• 餌の高さが大きいほうが良い
• まだ食べてない餌のうち、外側のほうが良い

これらを食べてきた餌ごとに足し合わせた累積和を評価値とした

chokudai幅は基本1、餌が少なくなってきたらchokudai幅を増やした

1ステージ当たり、イテレーションは100回～500回

山登り法

近傍はinsertとswapと区間reverse

どの近傍も2つの餌のペアを選んで作用させるが、距離の遠いペアは選ばないようにした

1ステージ当たり、イテレーションは10万回～40万回

その他高速化

餌を食べるターンは、その餌の高さをhとすると、h番目にたどりつくカメが分かればいいだけなので、sortやpartial_sortより速いnth_elementをした。

プログラムの中で一番時間がかかっていたのがnth_elementだったので、カメを1匹ずつ見ずに集団として見ることにした。