CODE VS

CODE VSに参加した。

予選は、総合部門3位、学生部門2位。決勝戦には学生のみ出場できて、3位(準決勝進出)。ソースコード

事前計算

実行する度にマップが変化するとのことだけど、マップは一部の障害物が出たり消えたりするだけ。敵は常に同じ。また、http://codevs.jp/codevs_client_public_cert.jarの拡張子を.zipにして解答すると、codevs_client_public_cert/resource/mapにマップと敵情報が入っている。例えば、2面のマップは、

7 9 1 0
1111111
1g00001
1010s01
1000011
1112001
1000001
1001001
1s000g1
1111111

こんな感じ。2がランダムに出現する障害物。敵情報は、入力のフォーマットと同じ。ただし、バグなのか仕様なのか、敵情報ファイルに何匹書かれていても最大で50匹しか読み込まれない。

変化が小さいので事前に計算しておくことにした。変化するマスは障害物として計算して、実行時にはレベル0ラピッド塔を配置すれば、少し資金が減るだけですむ。ただ、前半戦では無駄になる塔も多いので、実行時に塔を消してみて結果が良くなるなら消すようにした。後半戦は、障害物が消えることでより良い迷路が作れるかもしれないので、実行時に事前計算と同じ処理を少し行うことにした。

事前計算した結果は次のようにファイルに保存した。これなら手動で調整するのも楽。結局しなかったけど。

≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡
≡    R0    R0    R0 R0    ≡
≡? R0 R0 R0●R0R0 R0 R0○R0  R0R0 ≡
≡  ? R0  R0   ≡  ≡  R0 R0 ≡
≡ R0R0   R0  R0R0  ≡  R0    ≡
≡   R0 R0  R0 ≡    R0  R0 ≡≡
≡R0R0  R0R0 R0   R0R0≡≡  R0   ≡
≡  ?●   R4 R0    ≡  R0≡R0 ≡
≡   R0  R0R0  ≡R0R0  R0  R0  ≡
≡ R0  ≡?R4R4≡   R0R0  R0  R0 ≡
≡  R0  R0 R4 R0?   R0  R0 R0 ≡
≡R0  ?  R4R4   ≡R0  R0   R0 ≡
≡?R0 R4R4 ?? R0   ?  R0R0≡  ≡
≡≡  ≡R4  R4 R0 R4R0 R0    R0 ≡
≡  R0R4R4R4   ?  R4R4R4R0R0  R0 ≡
≡ R0    R4?R4○R4       R0  ≡
≡ R0R0 ?    ?R4R4R4R4R4R4R4R0 ●R0≡
≡    ? R0R0 R4R4R4R4   R0 ≡R0 ≡
≡ ≡ R0 R0   R4R4R0  ≡     R0≡
≡  ≡?   R0R0R0R0  R0  R0R0R0  ≡
≡≡?   R0≡   R0 ≡○R0R0   ? ≡
≡  ≡     ≡   ≡    ≡   ≡
≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡

共通

一定時間当たりの攻撃力を計算してみると、アタック塔は前半戦でも後半戦でも全く使い物にならない。

塔を途中で追加するくらいなら最初から追加しておいた方が得。壊す必要も無い。なので、塔を建てるのはレベル1のみ(そうでもないらしい。後述)。ただし、1面は資金が足りないので、別扱いして途中で追加する。

フィールド情報はint F[H][W]のような2次元配列ではなく、int F[H*W]と1次元で持っていた。こうすると位置を表すのに変数1個で良いし、要素にアクセスするのもちょっと速くなる、はず。

予選前半40面

前半戦は、

while ( true )
  if ( レベル1〜4のいずれかのラピッド塔を置くと資金が増えるマスがある )
    最も資金が増えるマスに塔を配置
  else
    終了

というだけのアルゴリズム。他の人に負けているのは、例えば出現マスが2個あって、タワーを1個追加するなら真ん中が良いけど、2個ならそれぞれの出現マスの近くの方が良い。という場合だと思う。

予選後半40面

敵の強さが一気に上がるので、出現マスから防衛マスまでの経路が長くなるようにタワーを配置して時間を稼ぐ。まずは、1個以外の防衛マスを塞ぐ。繰り返し、出現マスから防衛マスまでの敵の経路上で、敵が防衛マスに到達できないようにならずに、敵の経路が最も長くなる位置にタワーを配置する。という方法を使った。一工夫として経路上にこれ以上配置するマスが無くなったら、経路以外のマス全てにタワーを配置して敵の経路が短くならない限りタワーを削除という処理を挟んで↑の処理を実行するようにした。こうすれば経路が短くなることはないし、長くなることもある。出現マスが複数ある場合は、最小経路長*10000+合計経路長、とした。

あとは、勝てるようになるまでタワーを強化したり追加したりする。下の工夫をした。

  • 範囲内に敵の通るマスが多い場所を優先する。
  • 合流してからのほうが良いので、↑で敵の経路が合流したマスは合流数分でカウントするようにした。
  • レベル1タワーの値段はたかが知れてるので、強化→追加という順番にする必要は無い。
  • 強化・追加タワー数が多い方が常に攻撃力が上がるので、ギリギリのタワー数を二分探索。
  • 残りライフは評価されないので、ライフをわざと削って、タワーを節約。

あとは、この処理をひたすら繰り返して、各ステージごとに資金の少ない物を保存しておく。

何となく、使い物にならないと思い込んでいたけど、フリーズタワーは役に立つらしい。

決勝

基本的に予選後半と同じ。1面あたりの思考時間は500msくらいになるように、繰り返し回数を調節した。敵情報が事前にわからないので、レベルごとに塔の数を増やす。また、シミュレートで負けるなら、思考時間を増やして再度探索するようにした。

決勝出場者に配布されたデモプログラムでは39面が強くて、資金が残ったまま負けることが多かったので、生き残ることが重要だと思ったけど、この面が特殊で、本番は資金が尽きる方が早かった(´・ω・`)

その他

懇親会で聞いた話。強い敵は数が少ないので、その敵が出現するマスの距離を遠くすることが重要と。さらに、レベルごとに強い敵の出現マスが違う場合、途中で迷路を作り替える戦略がありえるのではないかと( ・∀・)つ〃∩ ヘェー ↓のような感じだろうか。

レベル1           レベル2         
↓こっちの敵が強い         こっちの敵が強い↓ 
≡≡≡≡≡≡≡≡≡≡≡≡≡  ≡≡≡≡≡≡≡≡≡≡≡≡≡
≡●R0   R0   R0●≡  ≡●R0   R0   R0●≡
≡ R0 R0 R0 R0 R0 ≡  ≡ R0 R0 R0 R0 R0 ≡
≡ R0 R0 R0 R0 R0 ≡  ≡ R0 R0 R0 R0 R0 ≡
≡ R0 R0 R0 R0 R0 ≡  ≡ R0 R0 R0 R0 R0 ≡
≡ R0 R0 R0 R0 R0 ≡  ≡ R0 R0 R0 R0 R0 ≡
≡ R0 R0 R0 R0 R0 ≡  ≡ R0 R0 R0 R0 R0 ≡
≡   R0   R0   ≡  ≡   R0   R0   ≡
≡R0R0R0R0R0R0R0R0R0R0 ≡  ≡ R0R0R0R0R0R0R0R0R0R0≡
≡     ○     ≡  ≡     ○     ≡
≡≡≡≡≡≡≡≡≡≡≡≡≡  ≡≡≡≡≡≡≡≡≡≡≡≡≡

コストはレベル0塔1個分だけ。