ハル研究所プログラミングコンテスト2019優勝　参加記

トータルスコア：約52000

以下リザルトページに乗ってる作品解説と同様

方針

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

ビームサーチの亜種である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匹ずつ見ずに集団として見ることにした