Topcoder Open 2015 Marathon Match(Round 2)の参加日記

6/9記載ミス修正。hogeover30さんありがとうございます。

マラソン初参加の前回（MM1）で53位/171人だった。今回は一気に上位2割を目標にしてみる。

前回の反省点は次のとおり。

グリッドの中に基地がいくつかある。（HP1000）
グリッドの端から基地までいくつかの道がある
グリッドは正方形で、Max20ｘ2060x60
道の端から、たまに虫が生まれる（HPは決まっている）
虫はランダムに、戻らないように道を進む
虫が基地に到着したら、虫のHP分、基地のHPが減る
基地に到着した虫は死ぬ
また、資金が用意される（初期値が規定される）
資金を使って、塔をつくることができる
塔は、攻撃力、攻撃範囲とコストがきまったいくつかのタイプがある
塔は、攻撃範囲にいる虫を攻撃する。１ターン１匹のみ
もし塔が虫を殺せたら、虫のHP分creepMoneyだけ、資金が入る
　→ 素で間違えていた。今回はそうでもないが、こういう見落としは致命的。問題はちゃんと読む。
全部で2000ターン
1ターンごと、塔を作ることができる（いくつでも）
塔は、基地および道には作れない
何回か、虫が一気に生まれることがある。Waveと呼ぶ
虫の総数は500から2000の間
虫のHPは、ターン500、1000、1500で倍になる
基地のHP合計と、資金の合計がスコア
最終スコアは相対評価

まず最初に前回の反省を踏まえてローカルのバッチ環境（クリック１つで複数のテストを流し、CSVで結果を吐く）の構築、および独自ビジュアライザの作成を行った。

ビジュアライザは、デバッグしやすいように、実行Log（メソッドへの引数が保存されている）を読み込んで、実際にメソッドを実行するようにした。さらに、グリッドをクリックすることで虫や塔などの情報を表示するようにし、また、前・次ステップへの遷移機能も付けた。

f:id:yambe2002:20150529152022p:plain

ここまでで4日も使ったのは失敗だったろうか。

残りの10日で実装した内容はこんな感じ。シミュレーションやモンテカルロは時間が厳しそうなので、貪欲にした。

はじめに全虫発生ポイントから全基地までの最短経路リストを作る（パターンが多すぎるときは最短２つの基地までにしておく）
そして、それぞれの塔パターンに、支配下にある経路、攻撃力、コストをもとにスコアを付ける
各ターンごと、虫が盤上に居たら次のルーチンを回す
　１、今の塔ですべて殺せそうなら何もしない
　２、殺せなかった虫が通りそうな経路（最寄の塔までランダム）を支配下にもつ塔を選ぶ
　３、そこから、購入できるもので最もスコアが高いものを建築する
　４、まだ生きてる虫がいたら２へ

暫定順位で61位/171人だった。目標達成ならず。

ソースコード

反省点

パラメタ調整にExampleケースを使ってしまった。少なすぎる。今回の場合、せめて30ケースくらいは回すべきだった。上位に比べると、明らかに調整がレアケース（シード10）に引っ張られている
テスタのコードをちゃんと読むべきだった。序盤、虫の経路について勘違いをしていて時間をロスした
パラメタ調整はやはり自動化したい
問題をちゃんと読む。虫を殺した時に入るMoneyに誤りがあった

次はRound3。今度こそ2割くらいに入りたい。