simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

MM131 StopTheElves 感想

問題

www.topcoder.com

最近オンライン問題多くなってきた。

方針

  • プレゼントを囲むように箱を設置する
  • 箱はすぐ設置するのではなくエルフが近づいたときに設置を行う
  • 事前にシミュレーションを行って防衛成功率の低いプレゼントは守らない

プレゼントを囲むように箱を設置

プレゼントの周辺マスをチェックして、このマスに対して凸包を求めます。この操作は毎ターン行います。

f:id:simanman:20211223235843p:plain:w240

f:id:simanman:20211224000523p:plain:w240

f:id:simanman:20211224000842p:plain:w240

求めたマスに対して、それぞれ最短路を求めてマス同士を接続します。

f:id:simanman:20211224001108p:plain:w240

箱はすぐ設置するのではなくエルフが近づいたときに設置を行う

箱を早く設置しようがしまいが結局エルフは箱 or プレゼントを持ち帰るまでフィールドに居続けるので、なるべく右往左往してもらうために箱の設置はギリギリまで待ちます。あと、お金は基本的に保持していたほうがあらゆる事象に対処出来るのでなるべくセーブします。

f:id:simanman:20211224002300p:plain:w240

f:id:simanman:20211224002316p:plain:w240

事前にシミュレーションを行って防衛成功率の低いプレゼントは守らない

実際にクエリを送る前にシミュレーションをある程度回してみて、防衛に成功する確率の低いプレゼントについては守る対象から外します。

感想

エルフ行動の優先順位をもっとうまく利用した守り方もありそうだったけど、そこまで考察 & 実装が出来なかった。ただプレゼントを守るだけではダメなのはスコア差から読み取れたけど、そこから何も進めれなかったので残念。凸包以上に効率的な守り方を見つけられなかったのもダメだった。(木が多いときはもっと効率的な守り方がありそう)