MM131 StopTheElves 感想
問題
最近オンライン問題多くなってきた。
方針
- プレゼントを囲むように箱を設置する
- 箱はすぐ設置するのではなくエルフが近づいたときに設置を行う
- 事前にシミュレーションを行って防衛成功率の低いプレゼントは守らない
プレゼントを囲むように箱を設置
プレゼントの周辺マスをチェックして、このマスに対して凸包を求めます。この操作は毎ターン行います。
求めたマスに対して、それぞれ最短路を求めてマス同士を接続します。
箱はすぐ設置するのではなくエルフが近づいたときに設置を行う
箱を早く設置しようがしまいが結局エルフは箱 or プレゼントを持ち帰るまでフィールドに居続けるので、なるべく右往左往してもらうために箱の設置はギリギリまで待ちます。あと、お金は基本的に保持していたほうがあらゆる事象に対処出来るのでなるべくセーブします。
事前にシミュレーションを行って防衛成功率の低いプレゼントは守らない
実際にクエリを送る前にシミュレーションをある程度回してみて、防衛に成功する確率の低いプレゼントについては守る対象から外します。
感想
エルフ行動の優先順位をもっとうまく利用した守り方もありそうだったけど、そこまで考察 & 実装が出来なかった。ただプレゼントを守るだけではダメなのはスコア差から読み取れたけど、そこから何も進めれなかったので残念。凸包以上に効率的な守り方を見つけられなかったのもダメだった。(木が多いときはもっと効率的な守り方がありそう)