HTTF2019予選:ばらばらロボット

はじめてのマラソン参加記。
結果は60位と，なんとも言えない成績だが，2桁順位とれるかどうかが実力相応かなと思っていたので，善戦したと思う。上位の方々も何人か記事を上げているので，これがどの程度参考になるものとなるかわからないが，記念に残しておこうと思う。

問題

A - ばらばらロボット
マラソンは問題を理解するのも一苦労だ。要求も難しく，問題文を読み切ったときはどうしたものかと思っていた。

正の点数を得る

最初にやるべきことは「正の点数を得る」(有効な提出をする)ことだと思う。これは本当に何も考えずに書いたプログラムを提出する。今回の場合は，周りは壁マス，その他は空白マスにするというものだろう。これは競プロやってますという人なら書けるレベルである。開始5分で提出した。
Submission #3572613 - HACK TO THE FUTURE 2019予選
これで80940点。これは1つの基準になる。何か工夫をしたプログラムを提出して，この点数より悪くなったら，よっぽど変なことをしている(もしくはバグ)ということである。
このときの様子をビジュアライザで見てみる。

これを見たときは意外と青が多いなと思ったのだが，緑や黄色も多いのでスコアは伸びない。
正の点数を得たので，どうやって得点を伸ばすか考える。

苦悶

ここから2時間は全くまともなことができなかった。いい感じの盤面を構成しようにも全然うまくいかない，ということを繰り返していた。
1つだけ考えたものを公開すると，周辺を2倍マス(D)で埋めるというもの。端に溜まりがちかと思ったので，端に来たら帰りやすくするようにしたかった。

Submission #3573461 - HACK TO THE FUTURE 2019予選

結果は微増。逆に端が疎になりすぎてしまった。

山登り法

2時間経ってから，マラソンの定番である山登り法を試していないことに気付く。これはあかん。
山登り法とは，端的には以下のような方法である。

1. 適当な初期状態を定める。
2. 現在の状態から，「少しだけ」変わった状態を作る。その状態の得点を実際に計算する。
3. その得点が現在の状態より良かった場合は，「少しだけ」変わった状態に遷移する。2に戻って繰り返す。

要は，今いるところより高い方に進んでいくという気持ちそのままである。この「高いところを探す→更新」という流れを制限時間いっぱいまで繰り返す。局所解に陥る可能性はあるが，それはもう仕方ない。(焼きなまし法はこの局所解に陥るという可能性を減らす方法であるが，実装できないので(おい)使わなかった。)
この問題における「少しだけ」変わった状態とは，あるマスの種類を別の種類に置き換えるというものであろう。よって，以下のようにして山登りを行った。

1. 初期盤面を「周りは壁，その他は空白マス」と定める。
2. 現在の盤面からあるマスを乱択で選び，別の種類のマスに置き換えてみる(これも乱択)。その後，実際にコマンドに従って体のロボットを動かし，得点を計算する。
3. その得点が現在の盤面より良かった場合は，マスの変更を採用する。2に戻って繰り返す。

やっていることは難しくないが，ロボットの動きをシミュレーションするなど，それなりの実装力が要求される。コンテストの時間は8時間もあるのだから，じっくり実装できる。多少バグらせたが，1時間程度で実装できた。結果はこちら。

青マスがだいぶ増えている。スコアも劇的に伸びた。これを提出すると113776点。やる気が出てきた。
Submission #3575341 - HACK TO THE FUTURE 2019予選

シミュレーション高速化(差分更新)

愚直な山登り法がとりあえず動いたので，この方向性でスコアを伸ばすことを考える。当たり前だが，山登り法は「高いところを探す→更新」というループの回数をできるだけ多くした方がよい。制限時間があるので，シミュレーションを早くすることでこの回数を増やすことを考える。上のプログラムのループ回数をAtCoderのコードテストで見たところ，1777回であった。
上のプログラムでは，あるマスを変えたときにすべてのロボットを動かしなおしているので，計算時間がかかる。ところが，あるマスを変えたときに，動きが変わるようなロボットというのはそこまで多くないはずである。よって，各ロボットについて，現在の盤面のときにどのマスでコマンドを実行するかということを記録しておく。すると，あるマスを変えたときに影響を受けるロボットがわかるので，そのようなロボットについてのみ操作をやり直す。これも実装力が要求されるが，時間があるので頑張る。これもかなりバグったが，なんとか実装しきる。結果はこちら。

さらに良くなったことがわかる。ループ回数は8232回だった。実装がよければもっと伸びると思う。提出すると得点は120148になった。順位表を眺めていて12万点は乗せたいと思っていたのでよかった。

さらなる工夫

ここからは問題固有の考察が必要になる(と言っても，ここからはあまり伸ばせなかった)。よく考えると，壁マスを置いてしまうと，ロボットの到達できるマスが減ってしまうため，ばらばらにしたいという問題の要求に逆行している。よって，壁マスは使わないことにする。あとは，角のあたりに2倍マスや3倍マスを置いてから山登りするとなぜかスコアが伸びたので，そうしたものを提出した。一応，角に集まり過ぎないようにするという作戦は微量だが効果を発揮したらしい。

Submission #3579046 - HACK TO THE FUTURE 2019予選
122547点。これが最終得点となった。この後，「コマンド列のどの時点どのマスにいるか」を記録して操作を最初からやり直さなくていいようにしようとしたのだが，バグが取れず間に合わなかった。

終了後

終了後に得た知見を少し紹介。

LとRだけ使う

自分はDとTだけ使うということをしていたのだが，シミュレーションの高速化上都合が悪い。無駄な動きが増えてしまうからである。これは気づきたかった。

初期盤面をLで埋める

これに気付いた人はすごい。すべてのロボットを左向きに回転させてから山登りするとうまく散るということらしい。
とりあえずこの2つの工夫はすぐに試せるのでやってみた。

Submission #3581258 - HACK TO THE FUTURE 2019予選
125545点に。ここまでやれば30位台に入れたが，気づかなかったので仕方ない。

コマンド列の圧縮

例えば，LRというのは何もしないというのと同じだし，SSSというのは3マス前に進むというのと同じである。こういう圧縮をすべてのロボットのコマンド列に適用する。これだけでコマンド列はかなり短くなるはずで(悪くても1/2くらいにはなるはず)，高速化にかなり効いている。

感想

実は1週間前からマラソンの勉強を少しだけしていて，その成果が出て12万に乗せられたのはよかったと思う。その先は問題固有の考察が必要で，これはアルゴリズム同様に鍛えていかなければいけないところだと感じた。焼きなましやらビームサーチやら習得すべき技術はあるが，結局問題の性質を掴めるかの方が大切そうと感じた。
終わってみれば8時間はあっという間で，非常に充実した時間を過ごすことができた。chokudaiさんとtsukammoさんに感謝します。
本戦オープンコンテストの日はバイトを入れようと思っていたが，オープンコンテストに真面目に参加しようと思う。

追記(11/13)

20卒だったら本戦オープン行けてたらしい。残念！