codingame fall-challenge-2020 参加記 ～最後までダイクストラ編～

contest

結果 Gold

f:id:peroon:20201123231039p:plain

  • ビームじゃなくてダイクストラで結構いい位置に行けたが限界を感じ、後半の追い込みはしなかった
  • twitterを見ているとlegendに行けると「おめでとう～」という感じで、終了後の感想戦(twitter, twitcasting)でも貢献できそうに思えた

今後学びたい

  • マラソンの2大手法としての「焼きなまし」「ビームサーチ or chokudaiサーチ」
  • 機会を見て学ばなければ（今回が機会だった説）
  • 公式サイトにはmonte carlo tree searchとも書かれていた。これはTLではあまり見られず、これを使うとワンチャンあるかも

やったこと dijkstra

  • 石の数とBREWを頂点としたダイクストラ。石が「1,2.0,3」ならそのまま頂点ID 1203とする
  • CASTを辺とするが、repeatable可能なものはrepeatできる範囲で増幅しておく。辺のコストはcastable, 得られる利益などから決める
    • コスパが良いならプラス
    • castableじゃないなら（休憩が必要なので）マイナス等
  • 石の評価は青から「1, 2, 3, 4」としたが、前半の青・緑をやや重み付ける人も多かったようだ
  • ダイクストラして、行けるBREWのうち行き先を決めたら経路復元し、その1手目を今回の動作とした

やったこと angry BBA

  • 6回目のbrewで勝負が決まるので、その局面では得られるjewelよりも早く作れることを重視した
    • 勝っている状況なら最速で作る
    • 負けている状況なら逆転できるものだけを狙う

やったこと evaluate learning

  • learn対象について、効率の良さや税金、予約の青石が付いてくるかなどで評価して、その評価が高ければ1番したじゃなくても取りに行くようにした
  • 払う石の「数」と貰う石の「数」の差が少ないほどrepeatableが回ると思ってそれも入れてみたが効かなかった
  • 「+1, +1, 0, 0」などの増えるだけlearnはrepeatable=0なのだが使いやすいという利点もあり、どう評価するべきか迷うが少し加点しておいた

困ったこと TLE

  • ダイクストラがたまにTLEする（50ms時間制限）
  • 頂点ID「9999」などありえないものを除去したとしても頂点数は1000～2000あり、それらから辺を生やすとO(N2)本ほどとなり、ギリギリ
  • 小さい変化のlearnが多い時にたくさん辺が張られるのでTLEしやすくなる
  • learnの最大数を8に絞るなどして抑えたが、それでもたまに発生していた。時間を計測して途中で打ち切るのはやらなかった

codingameで使えそうなURL