はじめに
CodinGameのコンテスト(CODINGAME SPRING CHALLENGE 2023)に参加しました
結果は世界82/5290位(Legend)、日本20/309位でした
🐜さん観察日記
ルール
例のごとくツカモさんの要約記事です(ありがとうございます)
tsukammo.hatenablog.com
やったこと
概要
方針:最初にある程度卵を集めて🐜を増やす、その後は距離順に最小シュタイナー木っぽくリソースマスをビーコンで繋いでいく
ルールベース + ダイクストラでの経路決め
BEACON
ビーコンの強さは1で固定
ダイクストラで求めた経路を復元し、経路上のマスにBEACONを設置
ダイクストラ
自分のベースとすでに設置したビーコンを始点としてダイクストラをする
(そのマスの蟻の総数 + 1)の逆数をコストとして最も近いリソースマスを貪欲に選ぶ
お気持ちとしては蟻が全くいない方向にビーコンを置くと移動に時間がかかるのですでに蟻がいる近くのリソースマスを狙うようにしたいため
選ぶリソースマスの総数は以下のルールベースで選択
現在の盤面に存在する卵のマスの個数を $ EggCells $、クリスタルのマスの個数を $ CrystalCells $ とする
- 取得した🐜の卵の総数が初期配置の🐜の卵の総数の15%未満の場合、最大 $ \lfloor \frac{EggCells}{2} \rfloor + 1 $ まで卵のマスを選択する
- 取得した🐜の卵の総数が初期配置の🐜の卵の総数の30%未満の場合、最大 $ \lfloor \frac{EggCells + CrystalCells}{2} \rfloor + 1 $ までマスを選択する、ただし卵のマスがある場合は卵のマスを優先して選び、残りをクリスタルのマスを選ぶ
- それ以外の場合、残っているマスの中から距離順に貪欲に選ぶ
マスを選ぶ際に相手始点でもダイクストラで各マスへの距離を求めておき、マス $ i $ の距離が $ OpponentDist[i] + 1 < MeDist[i] $ の場合は選択しない
境界付近のマスを除いて相手の方が近いマスは基本的には狙わないほうが良く、自分が取るべき個数(初期リソースマスの半分)+ 1個(中心に配置されているような自分と相手が争うマス)を取ることができれば勝てるため
やりたかったこと
・nターン後のスコア最大化(探索)
・ビーコンを上手く置いて🐜を賢く動かす(諦めた)
知見
焼きなまし(山登り)でビーコンの配置を最適化
感想
🐜の挙動を上手く動かすのが難しくてコンテスト期間中ずっと考えていたけど結局しっくりくる方法が思いつかず諦めた
シミュレートも書いたけど重すぎて結局使わなかったんだけどいい感じにシミュレートする方法あるのかな、気になる
とにかく何もわからなかったのでレジェンド行けて満足
おまけ(ブロンズ到達RTA)
瞬間1位の実績達成したので今日はぼくの勝ちでいい? pic.twitter.com/eVzVq04TvF
— ボンド@競プロ (@bond_cmprog) May 25, 2023
やったこと
リソースのあるマスを全部LINEコマンドで選ぶ(サンプルコード+数行)