TopCoder Marathon Match 98

TopCoder Marathon Match 98

コンテストページ

どうもマラソンの方が少し向いているらしいので
定期的に rated マラソンを開催している TopCoder のマラソンマッチに参加してみた．

問題概要

モンスターが跋扈するダンジョンに放置された姫を救出する
四隅から騎士を送り込むことができて，各ステップごとに各騎士に対して 4 方向移動の指示を出せる
姫とモンスターは 4 方向にランダム移動する
初期条件として姫の位置とモンスターの位置が与えられ，その情報を頼りになるべく多くの姫を救出し，なるべく多くのモンスターを殺す

やったこと

2/15

問題文をとりあえず見てみる．英語．量多い．死亡．

2/18

HACK TO THE FUTURE 予選がいい感じに終わったいい感じのテンションで改めて英語と向き合う．
なんとか問題文を理解して適当な自明解を投げつける．

---適当な自明解 (version 1)---
騎士パーティを 4 分割してそれぞれの入口から送り込む．対角線上を進ませて逆側の出口から出ておしまい．
-----------------------

Example scores:
0) 601.0
1) 1231.0
2) 115.0
3) 303.0
4) 1120.0
5) 329.0
6) 692.0
7) 307.0
8) 304.0
9) 903.0

Total: 5905

Overall score: 421312.5

Standings : 52nd

まあ初めてだしこんなもんだよな，ということで，夜も更けてきたので寝る．

2/19

ニートに平日もクソもないのでマラソンをやる．
寝起きに昨日の自明解を雑に弄ったコードを投げつける．

---雑な改変 (version 2)---
騎士パーティを 4 分割してそれぞれの入口から送り込む．
対角線上を時刻 S まで進ませて (時刻 S で騎士は中央に集合する)，
そこから時刻 S³ - S までランダムな動きをさせる (なんとなく姫の回収を狙っている)．
残り時刻 S になったら再び対角線上を進む命令を出して，逆側の出口から出ておしまい．
-----------------------

Example scores:
0) 601 -> 809 (+208)
1) 1231 -> 2839 (+1608)
2) 115 -> 248 (+133)
3) 303 -> 409 (+106)
4) 1120 -> 1194 (+74)
5) 329 -> 636 (+307)
6) 692 -> 988 (+296)
7) 307 -> 670 (+363)
8) 304 -> 314 (+10)
9) 903 -> 529 (-374)

Total: 5905 -> 8636 (+2731)

Overall score: 466144.58

Standings : 47th

差分計算してブログ用にフォーマット整えるコードを地味に書いた．いい感じ．

ここで英語を何度も読むのが苦痛になっていたので思い切って全文日本語訳をする．ニートなので．

解法を考えるにしてもいちいちバージョン変更して一個ずつシード指定して差分を調べてたら日が暮れるので，見よう見まねで Windows batch ファイルを作って一括実行するようにした．

@echo off
setlocal enabledelayedexpansion
cd %~dp0
for /l %%i in (0,1,99) do (
    java -jar .\tester.jar -exec "filename" -seed %%i
)

これを test.bat とか名前つけてコマンドウィンドウで実行すれば 100 テストケース一気に試すことができる．やったね．

で，試しに version 1 と version 2 の差分をとって比較してみる．

本当はサイズで正規化したほうがいいんだろうけど面倒くさいのでまだやってない．
明らかにスコアが良くなっているケースと，明らかにスコアが落ちているケースを比較したら何か見えてきそう．

明らかにスコアが落ちているケース

• 長時間ダンジョンに留まって騎士全滅

明らかにスコアが伸びているケース

• 騎士の数がモンスターの数に比べて充分多い
• 姫をたくさん回収した騎士がランダム移動でうまい具合に出口に到達している

というわけで，無駄に長時間ダンジョンに留まっているとモンスターに殺されることがわかったので，適度な時間で脱出するようにする． 中央到達から 100 turn ほど経過すると，姫はもうだいたい死んでるし騎士もバタバタ死ぬので，そこらへんまでランダム移動させた後で退散させることに．

---ちょっと改変 (version 3)---
騎士パーティを 4 分割してそれぞれの入口から送り込む．
対角線上を時刻 S まで進ませて (時刻 S で騎士は中央に集合する)，
そこから時刻 S + 100 までランダムな動きをさせる (騎士が死なない程度に姫の回収を狙う)．
以降は再び対角線上を進む命令を出して，逆側の出口から出ておしまい．
-----------------------

version 1 -> version 3 (diff)

version 2 -> version 3 (diff)


Overall score: 533793.10

Standings : 42nd

少し伸びた．
version 1 -> version 3 の差分グラフを見ると，version 1 -> version 2 の差分グラフにあったような極端なマイナス (-1000) は無くなっていることがわかる．
version 2 -> version 3 で比較すると version 2 で調子良かったやつが悪くなってたりするので，差し引きで微妙にプラスになったぐらいかなあ．

version 4

ENTER -> SPREAD -> GATHER -> DESTROY -> ESCAPE

ENTER
四隅から真ん中まで行く

SPREAD
ここから広がっていきます

このように

はい

GATHER 真ん中に集合

DESTROY めちゃくちゃ強くなったのでモンス蹂躙する

お掃除

ESCAPE 綺麗になったら脱出

これで 555691.49 の 43 位
意外と伸びなくてがっかり．

スコアが大きい(姫の初期配置が多い)データに対してはすごい伸びてるけど他があまりよくないらしい．
各テストケースにおいて参加者を倒した数で得点が決まる関係上，合計点をいくら上げたところで意味がない．

スコアに最も大きな影響を与えるのは救出した姫の数なので，rate = (姫の救出数) / (姫の初期配置数) をプロットしてみることに．

良いケースもあれば悪いケースもある．この差が何か調べてみる．

良いケース

• ぶっちゃけ偶然回収できたケースが多い．マップが狭くて騎士が多い場合とかは(まあ当然)うまくいく

悪いケース

• 最悪ケースでは最短で到着しても姫が全滅するパターンだった．これは除外するしかない．
• 姫が分布しているところから遠い入り口から入るとダメ
• SPREAD フェーズではマップの中心から広がっていくため，姫が中心から外れたところに分布していると全然ダメ．
• 真ん中に集合して広がるのは時間の無駄．その間にたくさん死んでるケースが多い

解決策

• 最悪ケースの場合は姫は見捨てて騎士を死なせずモンスターを殺しまくる方向に切り替える（できんのかな）
• 姫が分布しているところからなるべく近い入口を選ぶ
• 姫の存在位置の重心とか分散とかを求める．二変数ガウス分布とかでモデル化できるか？
• モンスターが多いところでは固まって行動するが，疎なエリアに入ったら散開して囲い込むように姫を回収する

この辺を実装すればいいとこまで行きそうな気はするんだけど実装重そうでアですね

2/20

生活リズムが終わって午後 7 時に起きた

寝起きで曖昧になっていたので最尤推定などをして遊んだ．何か後で使えるかもしれない．

ENTER 時と GATHER 時の集合場所を姫達の重心位置にセットして，姫の重心に近い入口から騎士が多く入るようにしただけで少し伸びた．

Full submission 6:
629455.45
35th

とりあえず 700000 くらいを目標にしていたのでいい感じではある．

ENTER 時にも少し分裂させてやるとさらにいい感じに．

Full submission 7:
699900.99
30th

ギリギリ 700k 乗らんかった．

ここでバグを発見する．
乱数生成を xor128() で行っていたのだが，unsigned long 型が VC++ では 32 bit なのに対し TopCoder 側では 64 bit になっていたため正しい乱数が得られていなかった．
これを修正するともう少し伸びた．(みなさんもお気をつけて)

Full submission 8:
732654.87
28th

朝になっていたので寝る．

2/21

最終日，だったが後輩のバンドである雨ガエルと出鱈目さんのライブを見に行っていたためあまり参加せず．

PV 良いのでおすすめです

www.youtube.com

酩酊しながら 5km くらい歩いて帰宅．意識混濁状態でパラメータ職人をやって少しスコアが伸びた．(ウケる)

Full submission 9:
750743.80
26th

当初の目標だった 700k を超えられたのと，マラソン初参加の黒色ネームの中では 1 位を取れたので割と満足．

HTTF 本戦も無事通ったので，健闘できたらいいなぁ．

以上，素人がマラソンマッチに参加してみた的記事でした．ここまで読んでくれた方ありがとうございます．