Codingame FallChallenge2020
情報少な目のDPをした。
GOLDの上の方だった。全体159位だった。
ルール
ポーションを作って金を得る。
金をたくさん持ってたら勝ち
4種類の材料がある。
常に5種類のクエリが存在する。
毎ターン行動を選ぶ。
相手と被った場合は両方が成功する。
こなされたクエリは消える。
スペルを唱えることで、自分が持っている材料を変えられる。
材料が11個以上になるようにはできない。
新しいスペルを習得できる。
1ターンで複数回唱えることのできるスペルもある。
スペルの習得は i 番目のものを習得するには i 個のレベル0素材を支払う必要がある。それぞれ i - 1番目のものに配置され、素材が配置されているスペルを習得する場合は、素材ももらえる。
6個作った人が発生したら終わり
左のやつにはボーナスがあるらしい。
やったこと
とりあえずできる中で一番利益がでかいものを選ぶことにする。
構造体とか、DEBUG出力用の関数も用意しておく。
(13日1:50)
Wood1昇格(13日2:15)
とりあえず無駄にはならないスペルも唱えてみることにする。
Bronze昇格(13日2:55)
とりあえずはじめはスペルを回収してからコスパが一番いいものを選んでみる?
DPで実装できそう。dp[スペルの使用状況][手持ちの素材]
それぞれ2^Nと14C4になる?
とりあえずスペル10個になるまで下から習得する。(17日3:00)
思ってるより重くてやばい(17日5:45)
スペルの使用状況無視してDPする。初回だけは使えるか判定できるので初回は判定する。一回でもアウトになって以降/2連続同じの使うは判定できないけど、大幅には変わらんやろ!w(17日8:00)
ジャッジ激重だったのでようやくシルバーになった(17日9:07)
スペル7個持たせてたのを12個にする。(17日9:18)ここでsilver240
明らかに強いのを敵に取られる場合があるので、それの対策をする。具体的には、取ることができるスペルの中で一番強いのを貪欲に取ることにする。但し、同利益ならrepeatできるやつを優先(17日11:30)260->150
repeatを別に優先しない?(17日11:45)150->160
DPの復元する際に、コスト軽い方から来たのを優先する。(17日16:30)なんも変化なさそうで困った。
持つスペル12->15個にしてみる(17日17:00)130->160
ポーションの評価に、最後に(作ってから/learn)終えてからのターン数を持たせる?(17日17:45)170->110
スペル12個に戻す(18日20:00)180->160
最後に(作ってから/learn)終えてからのターン数にミスがあったのを修正(18日21:30)170->170
ポーションの余りコストも何らかの形で考慮したい。多く余るものを優先する?
とりあえず諸々の価値が同じとき、多く余るものを優先するようにした。160->170
目指してるのと違うのを作れるようになっても無視する?した。180->200
スペルのバランスも考慮したい。自分の持ってる呪文のdifの総和の絶対値を小さくする方に引っ張る(19日2:30)レート43.3->GOLD昇格
これにも重み付ける?つけないことにする。
コスト(個数)の重さにペナルティを課す?めっちゃ弱い->めっちゃ弱い
スクロール読もうとして読めてない場合がありそう?(直した)190->130
プラスの和のminもでかい方が嬉しい?(19日12:15)140->200
ダメそうなのでこれはやめようかな
スコアに加えてあまりも同等に評価する?(19日14:15)200->90
この変更により、たくさん余るのを優先しないようにする。(19日15:30)90->100
累計のスコア、ターンで重み付けしてみる?あまりにダメそうなのでしない。
最後の1個を作る場合はあまりじゃなくて加算値で評価(20日15:52)170->160
相手が目指していそうなものを検出する?した。
目指しているやつを作れるようになっていて、相手が後1ターン以下で作れるなら即作る。(20日17:15)160->170
コスト(個数)の重さにペナルティつけるのをやめる。(20日18:45)180->140
あまりの計算がミスっていたのを修正(21日3:35)150->120
作れる時でも、ぎりぎりまで粘った方がよさそうな場合はそうする。(21日6:00)110->140?
粘らないことにする。(21日14:20)140->130
相手より遅くなりそうなものの優先度下げる(21日14:45)120->170
相手が即作れる時だけ無視する程度にする?170->140
敵が6個完成させそうなときも特別処理する。(21日16:00) 140->100
スペル10個にしてみる(21日16:30)90->190
スペル15個にしてみる(21日17:00)190->120
ある程度揃ったらスペル習得打ち切る。(21日17:30)120->110
即brewの条件を厳しく?(21日18:10)100->80
即brewの位置を調整 & 無視の条件のミスを修正(21日18:50)90->130
戻す(21日19:00)130->170
相手が5個になったら即brewする170->170
ターン数のカウントのバグを修正(21日20:30)150->110
プラスもマイナスも少ないものを得るのを優先?(22日14:00)180->130
わずかに高速化(22日14:55)
実装の変更(22日16:00)
高速化(22日16:50)
無視の条件のミスを修正、無料魔法の優先度を上げる、少ないものの調整を一度打ち切る(22日17:15)
TimeOutがきついのでdp部分でターン数が10より多く必要なものは無視することにした。(22日23:10)
ちょっと変えた。
消した部分と実装のマージ、スペルの調整するので、スペル12個にしとく(23日3:50)
青の補充したい場合に、tomeを見るようにする。(23日4:20)
習得時に青の支出も考える(23日4:30)
習得してスペルを使うのもするようにする。但し初手のみ(23日10:20)90->70
どちらかが5個作ってるなら次先に作るようにする?せんとく
即作る場合に、作れるものが複数ある時に対応
初手以外にもスペルのやつつける。
なんやかんやあってやってないこと
あと何手で作れるかが正しく計算できていなさそう?出来ていそう
全種類同程度に消費しやすい方が嬉しい?よくわからん。形を変えて実装した。
使用状況bitで持つのは無理だけど、集合は持つ?サイズで比較して小さい方が嬉しい。重いので無理そう。
初期魔法何回か使う場合に結構引っ張られていてつらい……つらいね。
無料魔法が少ないと……つらい!つらいね。