HACK TO THE FUTURE 2019予選 感想

こういう感想記事のタイトル、コンテスト名そのままだと検索の時にややこしいから「感想」とか付けた方がいいのかな。（そもそも検索に上がってくるほどアクセスが無い）

• HACK TO THE FUTURE 2019予選 - AtCoder
• 解説放送

マラソン形式のコンテスト。問題が長いので元記事参照。簡単に言うと、

• 29×29の盤面の中央から、500台のロボットが各々「右向く」「左向く」「1ます直進」のいずれかを300回行う
  • この300文字 x 500個の命令列が入力
• マスは、'.'平地マスの他、'D,T,L,R,#'マスにすることができ、それぞれロボットの行動に決まった影響を与える
• ロボットの最終的な停止位置を出来るだけバラバラにする盤面を求めよ

とりあえず正の点数を取るために、周囲を壁で埋めてTextで提出。

盤面の評価には、実際にシミュレートしてみないことには始まらなそうなので、シミュレーション実装。 （ただしスタート位置のindexを1つ間違えるというミスを犯す）

適当にランダムに盤面を決めて、評価して、いっちゃんよかったやつを出力。

'#'壁マスは多分罠で、最終的に止まる候補となるマスが減るし、突っかかって位置が揃いやすくなるしで、無い方がいいと判断。

'.DTLR'を同確率で埋めると、ALL平地よりスコアが悪くなった（ただしスタート位置を間違えて誤ったスコアで評価してたので当たり前）

'.'の確率を多くすると多少スコアがよくなった。 それも、かなり極端に80%くらいにした方がよくなった。あまり命令をいじりすぎるのも行動を狭める原因となるようだ。

後は出力をビジュアライザで眺めて遊ぶ。 今回、ビジュアライザからは「意外と何も工夫しなくても同じ場所で終わることって少ないんだな」くらいしか読み取れなかった。 4隅にめっちゃ留まるかと思えば、そうでも無い。

この辺でスタート位置の誤りに気付く。 が、それでもランダム配置では80000点台が頭打ちなので、盤面を徐々に改善していく方法を探す。

全て平地からスタート。

適当に1マス決めて、そこを適当に変化させ、スコアが改善したら採用。改善しなければ不採用。

115000くらいまでいく。ランダムの引きがいいと117000くらいまではいった。

で、これ以上の改善方法が思い浮かばず、終了。

解説を見ると、1回1回のスコア計算が重いので、山登りでも時間内に「山を登り切れない」ことがあるようだ。

確かに手元での出力盤面は初期状態からあまり多く変化してなかった。 平地が多い方がスコアがよかったこともあり「こんなもんなのか」と思っていたが、これは時間切れによるものだったようだ。

問題の時間制限を気にせず、例えば20連続くらい改善しなくなるまでやってみる。 それにめっちゃ時間かかるなら、スコア計算に高速化の余地があるし、焼き鈍しなどはその後の話となる。

今回の場合、'D'マスと'T'マスを諦めれば、命令'S'の行動は「1マス直進」で共通する。よって、'SSSSS'は、「5マス直進」とまとめてしまえる。

ここで'D'と'T'を諦めてよいのかの検証は、実際に抜いてみて、スコアに大きく影響しないことから判断できる。

また、'L,R'の連続も、まとめてしまえる。

ある1マスを変化させたとき、最終的に停止位置が変わるのは、その上に一時停止し、命令'L'か'R'を実行したロボットのみ。（上記の取捨選択後）

スコア再計算で行動をシミュレートしなおさなければならないロボットは、かなり厳選される。

そのロボットも、はじめて変化マスを踏むまでの行動は変わらないので、途中からシミュレートすればよいことになる。

さらに、そのマスで停止したロボットの最終停止位置が全て1台だった場合は、改善の余地が無いので、スコア計算自体を省略できる。（局所最適解を逃れるアルゴリズムの場合はまた変わってくるが）

この辺まで来ると実装がちょっと大変そう。

隅の方には、（意外と溜まりづらいとはいえ）中央と比較すると溜まりやすい。 そこで、盤面の初期状態を全て'L'または全て'R'にすると、常に同じ方向に曲がるので

• 壁にぶつかっても数回の方向転換で確実にぶつからない方向に方向転換される
• ぐるぐる回るので、同じ方向に'S'がそれなりに連続しない限り、隅の方に行きづらい

という利点がある。「なんとなく初期状態は平地」という固定観念があったが、なるほど。。。

ビジュアライザのソースコード(javascript)という、実装済みのが既にあるので、それ見りゃよかった。