てきとーな日記

2010-10-21

[]TopCoder Open 2010 02:05

マラソンで奇跡が起きて優勝しちゃった!

f:id:wata_orz:20101021234624j:image

Marathon Final

今年から24hになったので大変だった・・・

問題概要

崩壊する洞窟からコインを回収するゲームのAIを作成せよ

通路は単位時間で1歩移動でき,壁を壊すのにはT時間かかる

通路上にはところどころにコインが落ちていてその上に移動すると回収できる

崩壊は毎時間一定の確率で起こり,崩壊が起こると周囲のDマスが一気に壁に変わる

コインが埋もれると消滅してしまう

運悪く,崩壊に巻き込まれた場合はゲームオーバー(0点)

最初はマップの左端にいて,左端か右端にある出口に到達すると脱出成功となり,回収したコインの個数に比例した点数が入る

マップの難易度により重み付けがされ,各マップに対するスコアの和で順位が決まる

自分の解法

基本的にはダイクストラして一番近いコインを見つけ,てきとーなタイミングで帰還するだけ

マップがそこそこ広いが,目的地に到着したときと,目的地までのパス上で崩壊が起こったときだけ計算すれば十分な上,一番近いコインは結構すぐ見つかるので,なんとかなる

あまり遠くに行ってしまうと帰れなくなるので,コインを取って帰還する間に埋もれて死んじゃう確率をてきとーに見積もって,取りに行ったほうがよさそうな位置にあるコインのうち,一番近いのを狙うようにした

どれも取りに行かない方がいいと判定されたら帰還する

帰還するのにかかる時間の計算は,一番近いコイン見つけるのより時間がかかるので,1000ターンに一回だけ計算しなおすことにした

ビジュアライザ眺めてたら,たったひとつ取り残したコインを回収しに行って,そのせいで脱出が遅れて死んでしまうことが時々あったので,コインの周りに他のコインがどのくらいあるかも考慮した(コインがいっぱいあるのでマンハッタン距離で代用したが,意外とBFSでも速かったらしい)

結果

システムテスト前は2位だったけど,中には1ケースで0.5くらい取れるのとかがあるため,そういうのでたまたま運悪く死んでたりする可能性があるからあんまりあてにならないなーと思っていたが,意外とシステムテストで他の人達が点数伸びなくて,なんと1位になってしまった!

Algorithm Semi Final

マラソン終了後3時間くらい睡眠をとってから挑んだ

250

やるだけな感じの問題

なんかバグるーと思ったら,スワップを

int[] tmp = crt; crt = next; next = crt;

とか書いてたorz (最後がcrt→tmpが正しい)

500

品物集合を二つに分けて,平均価格の和を最小化する問題

寝不足+オンサイト補正(オンサイトだし激ムズに違いない)により解けなかったorz

冷静に考えたら簡単だったし…もうだめぽorz

1000

サイズ制約がどう見ても二つに分けてくださいと言っていたので二つに分けてRangeTreeだー!と思って組んでたがどっかバグってサンプル通らずorz

てか冷静に考えてBITでいいし…なにやってんの俺orz

Challenge

ACRushの250開いたらなんか7重ループが見え,それぞれ最大50回る感じだったのでエェ…と思って撃墜しそうになったが,冷静になって考えたら全体で50C7で間に合ってることに気づいた

他のは怪しいのすらなかった

System Test

8位orz (7位までならWildCard進出)

オンサイトはあまり得意じゃないがさすがにこれはひどいorz

感想

マラソンは夕飯食べたくらい(10h経過くらい)で体力の限界を感じ,そこからは定期的に横になって休んでた

てか,普段のマラソンもコーディングとかあまりせずに,ベッドで転がって方針考えてるのでこういうスタイルで最初からやったほうがいい気がした

アルゴリズム敗退して自分の出るのが全部終わった後は,カジノに入れる年齢になった+超アクティブな社員(大学のクラスメイト)を連れていったため例年よりいっぱい観光して,すごいハードスケジュールだったけどその分面白かった

ラスベガス4泊のはずが2回しか寝てないし…

社員が英語ペラペラでカッコ良かったので自分もいい加減英語何とかしたいなぁと思ったがなんともならないorz

あと,来年はダブル優勝目指す!(無理ゲー)

トラックバック - http://d.hatena.ne.jp/wata_orz/20101021/1287680741