CodinGame Spring Challenge 2023 解法まとめ
-
- いいね！0
bowwowforeach
@bowwowforeach
ジャッジのコードを移植したけど、びっくりするぐらい無駄な探索が多かった。ルールを理解して書き換えたらかなり高速になる。
2023-06-05 17:47:52
ヴァル
@ValGrowth
@bowwowforeach アリの移動経路は最短経路の中でしか変化しないので最短経路の１歩目だけ調べればよくて、Refreeコードで毎回目的地までPathFindingしてるのが省略できるって感じです。 「目的地への最短経路の１歩目の中から、アリ数とビーコン数が最も多いセル」を選ぶ処理は毎回必要です。
2023-06-05 17:43:44
いなにわ
@inani_waon
こどげ方針 ・目標構築は最小森 ・ビーコンは等分 ・卵だけ狙う→蟻数負けが無さそうになったら両方狙う ・基地との距離が敵の倍以上あれば諦める
2023-06-05 17:05:17
いなにわ
@inani_waon
卵を優先する→アグロに負ける 先を狙いすぎるのを直す→先に進む力が弱くなる 近距離を太く結ぶ→経路の大きな変更が多くてロスタイムが増える と、良さそうな方針も結果的に悪くなることが多くてきつかった
2023-06-05 17:09:22
いなにわ
@inani_waon
「〇〇すると強い」が色々な他の要素に引っ張られて人によって違うので、迂闊に他人を参考にしてはいけないタイプのコンテストだった気がする
2023-06-05 17:43:27
じろう
@Jiro_tech15
ビーコンへの変換は、各蟻の移動先を最小費用流でいい感じに決めた後に、javaのコードと同様の順序で(Ant, Beacon)を確認していき、その(Ant, Beacon)によって蟻が目的地に向かうなら貪欲にBeaconを置く、をしました(多分最適)
2023-06-05 17:12:22
じろう
@Jiro_tech15
拠点を根、リソースの存在する点を頂点、辺上の1マスあたりの蟻の数をCapacity、とした根付きフロー木を使って探索書いたものの、蟻さんはfloatじゃないので微妙でした
2023-06-05 17:09:04
じろう
@Jiro_tech15
理想通りに動かすビーコン配置があるなら貪欲で求まる(多分)けど、解がない時にマシなビーコンを求める方法が思いつかなくて、割り当てられなかった蟻をその場待機させるようにした結果崩壊した 山登り/焼きなまし かー 確かに
2023-06-05 17:18:12
るてん
@ruthen71
- ビーコンと資源マスを頂点とみて、頂点間の最短路を前計算しておきMSTを計算（途中で打ち切る） - 公式の実装をまねすればアリの移動をシミュレーションして獲得資源量を計算できるのでビーコンの配置を焼きなますgithub.com/CodinGame/Spri…
2023-06-05 17:12:18
いちご
@itigo_purokonn
大局の戦略をルールベースで決定して、ビーコンに対して蟻がどう動くかはシュミレーションできるのでビーコン配置を焼きなまししました
2023-06-05 17:06:32
いちご
@itigo_purokonn
焼きなましの評価関数は「直後のターンの収穫量」、「ルールベースに近づいてるか」で作りました 蟻のシュミレーションを限界まで高速化すると700~3000回程度焼けます
2023-06-05 17:08:20
いちご
@itigo_purokonn
評価関数によっては「同じスコアの違う状態」がめちゃくちゃ大量発生するので同点の遷移を許した山登りと焼きなましほぼ変わらない(同点遷移を許さないと、明らかに弱いけど)
2023-06-05 17:28:25
いちご
@itigo_purokonn
最初のターンに卵の優先度とchainの大きさを決定するシュミレーション書いたけど、なぜか弱くなったので結局マジックナンバー埋め込みした
2023-06-05 17:38:46