TopcoderのMarathonMatch131に参加しました。
問題はStopTheElves。防衛ゲーム的な問題でした。
結果は提出51人中、暫定テスト15位、システス12位でした。
問題
地面にプレゼントが散らばってるよ。
外周からエルフがプレゼントを奪いに来るから、自腹で障害物の箱を置いて被害を減らしてね。
考察
ルールを翻訳したらエルフの産卵率とか出てきてびっくりする。*1
TDっぽさと、一発OKが出なくて改修されたルール感をひしひしと感じる。*2
サンプルは最長路っぽいことをしている。でもプレゼントを完全に囲えば箱しか奪われなくなるので、その方がいいのでは？プレゼントは100円に対して、箱は1～10円だし。
エルフが複数いるときの動き方が明文化されていないので、解析や実験してみないとよく分からない。往路エルフと復路エルフの経路をバッティングさせてデッドロックとか出来ないのか？ → 出来なさそう。
となると、エルフが何かを持ち帰ること自体を食い止めるには、閉じ込めるか、目標位置を切り替えて右往左往させるしかない。ただ、これが本質かというとかなり怪しく感じる。それらをしないならエルフは何かを奪って帰るので、一時的な時間稼ぎにはあまり意味が無い。意味があるのは完全に囲うまでの時間稼ぎと、終了間際くらいか。あくまでプレゼントの代わりに箱を持ち帰らせることがメインになりそう。
これ、ポップ地点が箱で塞がってたらどうなるんだろう？湧き潰しで完全にエルフが出なくなったりする？ → 外周には箱を置けない。あ、はい。問題文に書いてくれ。
elfP * Cが[箱1つ設置する時間]に対する[エルフが湧く数]なので、これが1.0以下ならエルフに箱だけを持ち帰らせることが可能。そういうケースは全体の3/4で、残り1/4は箱の供給より奪われるペースの方が速い。ただ安全寄りのケースでも壁を構築しきるまでプレゼントを奪われるのと、危険寄りのケースでも一部を食い止めながらNNターン耐えることは可能。*3
うーん、最小の囲いを作ることが前提で、それまでの被害を抑えたり、終了間際だけ頑張るゲーム…？すごくつまらなさそう。最長路的なものを頑張って作っても、結局それは最小の囲い＋幅1通路だし、明らかにそれより先に囲いを作り切った方が良さそうなんだよね…。一応、elfP * Cが大きなケースでは囲い作りを放棄して外周のいくらかを割合カットする手法が取れそう。ただ箱の節約にはなるけど大事なのはプレゼントで、ランダム湧きに対して想定通り稼働するか怪しい。
ところで最小の囲いを作ると言っても、それは容易ではなさそう。途中いくつかは奪われるということは、守るべきものと捨てるべきものも決めないといけないだろうし。真ん中のものほど復路が長くなることを考えると、真ん中を残すのが良さそう。囲う方法としては、大きな矩形で全部囲うというのは思いつく。あとは角を取って八角形に出来ると嬉しそう。木を利用して動的に生成するのはきついかな…。矩形だとしてN=10で箱16個、N=30で96個が最大。あとは個別に囲う場合はP * 4個になるか。
実装
57点解法
とりあえず、大きく囲うか個別に囲うかしてみる。
そのまま置くだけだと余計な箱や隙間があるので、貪欲に縮小してみる。
→1マスずつ縮小しては密閉を維持できてるかの判定が間に合わない。スコアも落ちる。
余計な壁を消すだけに留める。
75点解法
早々に置き始めても、壁が完成するまでに中身が奪われてしまう。また、頑張っても結局間に合わずに全てのプレゼントが奪われてしまうことも多い。
今置き始めたらどうなるかを計算して諦めるかを判断したり、完成の目途が立ってから置き始めるようにする。*4
76点解法
複数の隣接したエルフに壁をこじ開けられたり、閉じ込めているプレゼント持ちのエルフを開放されてしまうケースが目につく。完全に壁を作って、エルフの隣に箱を置くことで安定させる。また、終盤以外も時間稼ぎに意味はないので隣に箱を出して即お帰りいただく。
80点解法
一度壁を置き始めたら場所は再考しないようにしていたが、既に無いプレゼントを守るための不要な壁を置いてしまう。プレゼントが持ち上げられた2ターン後に再考を走らせる。*5
まだ矩形と個別囲いしか出来ていないので、八角形の囲いを実装する。8方向の隅からの距離をセル毎に事前計算しておいて、プレゼントのMin - 1の位置を基準にする。全ての方向に対して基準を満たすセルを抽出すると八角形が取れる。このままだと中も塗りつぶされているので、最低1方向に対して基準をギリギリで見たしているセルに限定することで外周が取れた。*6
絶対スコアが凄く伸びたので、調子に乗って十六角形版も作る。こっちはそんなに伸びなかった。斜め部分を多くすることが重要だった？
79点解法
下がってませんか…？
1マスだけ塞げば外周7マスからの侵入を防げる、みたいな場所が存在する。*7
ここを塞ぐだけでは割合で防ぐ以外の意味が無いのだけど、メイン壁を作る前にここを塞ぐことで、壁を作る時間を稼ぐことが出来る。1マス置いて外周を1マスでも塞げるなら何も考えずに採用するという最悪な方法で手元スコアが伸びたので、何も考えず提出。
本当は外周の木2つの間をDPして最低接続コストを求めたりしたかったけど、ここで時間切れ。
他の人の解法を見て
プレゼント毎に、守るか守らないかを丁寧に決めるのが強そう？
プレゼントを持ったエルフを囲えば、時間稼ぎしつつ内側にも防壁を作れるので自然と良い形になる、みたいなのがありそう。密度の低いマップだと微妙かもだけど。
異端解法(後日談)
elfP * Cが大きなケースで、囲い作りを放棄して外周のいくらかを割合カットする手法。場所は自分が目視で決めて埋め込みました。
感想
方針がシンプルで実装が面倒、期待値計算で詰めるタイプの問題でした。
頑張って防衛を続けても、プレゼントを全て奪われると何もしない場合の1/100以下の点数になることもあるという苦行で、かつ相性で良くなったり悪くなったりも多いので、分かりやすく改善を楽しめるタイプの問題ではなかった気がします。
HTTFの疲れもあり出るか迷ったのですが、ある程度コードを書いてしまったので書いた以上は出すことにしました。
当初のコンセプトを曲げたような問題は怪しくなりがちですね…。
こういう問題だとせめて実装面で新しい知見が欲しくなるもので、その点では八角形の作成や、考察だけでしたが2つの木の接続といったものがあったので良かったです。
