olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

codingame (Code of Cutulu)

ルール

最初正気度を250持っていて、毎ターン4~6正気度を失う。ただし、2マス以内(壁を挟んでもよい)に他の冒険者がいると1~3で済む。

 

敵はトンベリみたいな見た目のものと死神みたいな見た目のものがいる。

前者は毎ターン1番近い人を追いかける。冒険者と重なると攻撃し、消滅する。また、30~40ターンで自然消滅する。

後者も基本の移動は共通だが、視界に冒険者が入ると2ターンのためののち、まっすぐに突進攻撃してくる。(突進に限って1ターンの移動制限がない)その後スタンする。また、消滅しない。各冒険者の正気度が最初に200を下回った瞬間にその冒険者と同じ場所に出現する。

どちらのモンスターも出現後6ターンは行動しない。

敵に攻撃された際のダメージは20ダメージである。

 

フィールドは空きマス、壁、モンスターのスポーン地点、シェルターで構成されている。

トンベリは5ターンに一度任意の冒険者から一番遠いスポーン地点から出現する。

シェルターは重なると上にいる冒険者の体力を5回復する。しかし、シェルターは50ターンに10しかエネルギーが回復せず、最初はエネルギー切れしている。

 

冒険者は毎ターン周囲1マス以内に動くか、特技を発動することができる。

PLAN…5ターンの間自分の周囲2マス以内の冒険者を3回復させる。2回使える。

LIGHT…3ターンの間他の冒険者がいるとよい範囲が4マス伸びる。3回使える。

YELL…2ターンの間周囲1マスの冒険者の動きを止める。何度でも使えるが同じ相手には1度しか効かない。

 

やったこと

ちょっと遅れて参加したので参加したころにはSILVERまで解放されてた。

開始時

トンベリを避けつつほかの冒険者と群れるのが一番大事だと考えたのでトンベリと他の冒険者だけを考えてマップに評価値を定めた。

具体的には任意のマスについて、任意のトンベリの最短攻撃到達時間、任意の冒険者からの最短距離を求め、敵に近すぎる場合は補正を加え、確実に安全なマスのみを通っていけるマスで評価値の一番いいところに近づくようにした。

このコードでSILVERまで上がった。

 

SILVER

死神についても最短攻撃時間を求め、トンベリのものと混ぜ、評価値を更新することにする。また、YELLを、自分が敵から2マス、ほかの冒険者が敵から1マスにいる且つほかの冒険者と接していてまだ使ったことがない相手であるときにYELLを発動することにした。

このコードでGOLDまで上がった。

 

GOLD

その場にとどまろうとするときにPLAN、LIGHTなどを使うようにした。

また、行き止まりに対してペナルティを定めた。(終了直前にわかったことだが不完全だった。)

パラメータガチャをしつつLEGENDにあがる。

 

LEGEND

シェルターの存在を忘れていたので実装するも劣化したのでシェルターを無視することにする。

また、行き止まり判定を行おうとしていたが、O(H^3 W^3)とかで悲惨だったため高速化するが、バグったためあきらめる。

 

やりたかったこと

・LEGENDでできなかったこと

・探索

 

レジェンドリーグまで上がって世界41位日本5位でした!うれしい!