TopcoderのMarathonMatch140に参加しました。
問題はRobotPainter。Forとか使って命令する系の問題でした。
結果は提出32人中10位でした。（事前テストも10位。）
問題
目標となるグリッド（トーラス環）を与えるので、ロボットに命令を与えて絵を完成させてね。
考察
これアプローチいっぱいありそう。ざっと考えただけでこれくらい出てくる。
・多くのセルを塗れるFor文を探す
・線の集合とみなしてTSP
・命令を木探索
・命令を全探索
一番上のはHTTFで高橋君メイドロボがやってたやつ。ただ今回は白マスに入ると大きなペナルティが付くのと、塗り残しが1,2マスあると結局線を塗りなおさないといけないので隙間だらけの塗り散らかしをするのは難しい。
線を塗りきることを考えると線を抽出して塗り順をTSPするのが良さそうな気がするが、「ここは別の線で塗るから1歩手前に止まっていいよ」とか「ここは1周できるから好きな場所に止まっていいよ」を上手く計算できる気がしない。
Forを考えるのも†全て†を考慮すると計算量が爆発するので、何か筋の良い方法はあるんだろうなぁと思いながらForはスルーして探索することに。
最終的にやったこと
N6～18はchokudaiサーチ。N19～30は貪欲法。
貪欲法
「残り塗り数 * 200 + コスト * 100」が主に最小化されるよう、「回転→F or B」を行う。無理なら浮かせてそのままの向きで移動したり、Jump。
時間いっぱい試行するが、2回目以降は評価関数の重みをランダムに決める。残り塗り数は11～199、コストは11～799。
申し訳程度に、以下のループを試行毎に10%の確率で1回だけ試す。*1
For 5～10
F (N-1)
J (任意)
End
chokudaiサーチ
ある程度の操作単位で区切って探索する。回転→移動が1セットとか。
無駄な動きは出来るだけ刈る。F 1→F 1とか、Up直後にDownとか、塗り済みの場所にJumpした後再Jumpとか。*2
状態遷移図を書いて刈るべき動きを見定め＆定義したり、それとは別にifでチェックしてフラグを立てたり。
感想
独創的なアプローチが見つかったり各々でアプローチが違えば本当に楽しそうなコンテストだと思いました。結局最後まで良いアプローチが見つからず、若干の消化不良…。
最近は多態性で殴ることも増えてきたのですが、複雑なことをするならやっぱり新しい言語バージョンでやりたいなぁの気持ちがありますね。マラソンだと単一ファイル、実験前提なので書き殴りになりやすい、みたいなのがありどうしても汚くなるので、そのうえバージョンまで古いとなると、どうも先に繋がるコードを書けている気がしない…。
