2018/11/10に行われたオンラインマラソンマッチコンテスト「HACK TO THE FUTURE 予選」に参加しました。
正のスコアを得た参加者が518人いて、僕は86位でした。20卒枠で本戦に呼んでもらえたので良かったものの、もう少し高い順位を取りたかったというのが正直なところです。
縦横29マスの盤面が存在して、500台のロボットが中心に上向きでセットされている。それぞれのロボットは長さ$L$の命令列をもっていて、その命令列は
の3種類の命令で構成されている。各ロボットは300ターンかけて命令列の通りに動く。プレイヤーは、これらのロボットが300ターン後にできるだけばらばらな位置に停止するような盤面を構築する。盤面には
という6種類のマスを配置することができる。300ターン経過時にロボットが1台しかいないマスの数だけ+10点、ロボットが2台いるマスの数だけ+3点、ロボットが3台いるマスの数だけ+1点がスコアに加算される。
山登りをしました。盤面のランダムな場所をランダムに変化させて、毎回ロボットをシミュレートし直していたので計算量としてはかなり大きいです。高速化の工夫として、盤面を4×4に16分割して、変化した座標の所属するエリアを通るロボットだけシミュレートするということを行いました。盤面については、".", "#", "L", "R"の4種類だけで構成し、"D", "T"を使わないほうがスコアが高くなりました。
マラソンマッチは通常1週間以上の長期にわたって行われることが多く、その場合には最初の1日を問題を分析したり方針を考えることに使えるのですが、8時間のマラソンマッチではとにかく最初に自明な解を作ってしまったあとに改良していく方法でないと時間が足りないらしいことは今回感じたことですね。短い時間しか与えられていないのは参加者全員同じなので、自明解をきちんと書くだけでもそれなりの順位に収まる感じがします。今回、更新のたびにロボットの起動をシミュレートすることで計算量が大きくなりすぎることを恐れて最初の2時間程度あまり動けなかったのは反省点だと思います。
最終的に使ったマスは".", "#", "L", "R"でしたが、このうちで"#"は使わないほうがよいスコアが出がちだったようです。理由としては、ロボットをできるだけ様々なマスに散らばらせることを目指しているのに壁を設置してしまうとその候補を潰してしまうからということのようです。自明な解を書いたあとの改良について、もう少し計算量を落とすことを考えるべきでした。空間計算量はもっと大胆に利用してもよかったので、各ロボットが通ったマスを覚えておいて、変更があったマスを通ったロボットを、変更があったマスからシミュレートすることで上位の人たちは計算量を落としていたようです。
本戦に通ってよかったけど、反省点も多いマラソンマッチでした。ハーフマラソンでの戦い方がわかったのはよかったです。