HACK TO THE FUTURE 2019予選 ばらばらロボット
概要
73位/519 でしたが、20卒枠で予選通過しました。
コンテストに参加するにあたって以前のコンテストの参加記に助けられたので自分も記録を残します。
コンテスト参加までにやったこと
この予選がマラソンコンテスト初参加でした。
ビームサーチや焼きなましなどの単語は知っているけれど何をしているのかは分からないぐらいの地点からスタートです。
とりあえずいくつかの解説記事を読みながら HTTF2018 予選 山型足し算*1 を解きました。主に以下の解説記事を参考にさせていただきました。
乱択・山登り・焼きなまし辺りを書いて予選4位ぐらいの得点が取れるようにしました。ついでに XorShift をライブラリ化しておくと便利です。
コンテストでやったこと
高得点を取る方法については他の方の解説記事にお任せします。
問題概要
- 'S', 'L', 'R' からなる命令列が複数与えられる
- '.', '#', 'D', 'T', 'L', 'R' からなる盤面を構築する
- 盤面上で命令列を実行し、全ての命令が実行された後の状態に応じ得点が得られる
- 30ケースに対する得点の和を最大化したい
(各命令の意味及び得点計算式は問題文参照)
解法
やったこと
- 適当な盤面から山登り・焼きなまし
- 初期盤面は '.' で埋めておく(最終的に 'L' を適度に撒いておくようにした)
- 評価関数は与えられた得点計算式をそのまま使う
- 盤面構築には '.', 'L', 'R' 以外は使わない。この3種類の配置・撤去で遷移を行う
'T', 'D', '#' を使わなかった理由は 'L', 'R' だけで十分な解空間が確保できると考えたためです。シミュレータをバグらせたくないという理由もあります。
最終的に山登り回数は 4000回程度になりました。
やらなかったこと
- 変更したマスを通るロボットのみを対象に得点を再計算する
- 変更したマスで回転するロボットのみを対象に得点を再計算
このどちらかを実行していれば山登り回数を増やせることは分かっていましたが、実装しきれるか自信が無かったので諦めました。
結局最後の3時間は暇していたのでやるべきだった。
気づかなかったこと
- 初期盤面を 'L' で埋めておく
- 命令列の圧縮
何を食べたら 'L' 埋めに気付けるんでしょうか・・・
感想
- 基本的な山登りができれば(20卒枠通過には)十分な点数が取れる問題だった
- さらに上位を目指すには考察・実装が重そう
- 夕飯*2を食べた後力尽きたのは反省
- 最後の方は焼きなまししていたが、山登り高速化の方が優先度高かった(焼きなましで一応点数は上がった)
