今週土曜日、診断人さん主催で12時間マラソン練習会が行われました。
今回使用した問題は「TCP2010 CollapsingMaze」
http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14411&pm=11140
内容はざっくり説明すると
「コインがばらまかれた迷路があるので、なるべく多くのコインを拾ってね。あと、たまに迷路が崩落するけど巻き込まれないように気をつけてね。」
こんな感じでした。（違
最初は、A*を使用してコインまでの経路を求めていたのですが、後々考えると、細い一歩道が多めだったので、それならBFSかDFSでも十分精度の高い経路になったんじゃないからと思いました。他の参加者はダイクストラやBFSを使用していたみたいです。
今回の問題では特に、「戻るタイミング」が全然思いつかなかったので、迷路のサイズに合わせてタイムリミットを設け、その時刻を過ぎたら帰還するようにしたのですが、あまりよろしくなかったみたいです。崩落の頻度とか規模を記録して、期待値とか出せばよかったのかなー。
あと、戻るときもスタート地点に戻るんじゃなくてなるべく反対側から帰るようにしたほうがよかったですね。
久々のマラソン問題でしたが、ダメダメなところばかりでした。12時間という制限からかコードの質もちょっと悪くて、全体の1/3はデバッグに時間を取られた気がします。次回に向けて練習頑張りたいと思います。
