HACK TO THE FUTURE 2019予選の反省

AtCoder マラソンマッチ

beta.atcoder.jp
7位/519でした。
今回は、意地でも定番解答にはならない問題をchokudaiさんが作ってくるかなと思ったら、わりと定番だった。見えることを１つ１つ改善していけば、点が増えていきやすいタイプ。
…と思いきや、後半に、いろいろ考察をちゃんとしてれば、加点できる要素があったので、上位から下位まで、実力が出やすい問題だった気もする。
tsukammoさん、chokudaiさん、ありがとうございました！

良かったこと

  • 天才解法を考える誘惑に負けず、簡単なところから行ったのが良かった。
  • 決勝に出れないのは分かっていたけど、ちゃんと最後までがんばった。もう衰える一方の年齢なので、老化防止のために、がんばるべきときにがんばるのは重要。

反省すべきこと

  • 残り2時間で伸びなかったのだけど、条件が変わった後の再考察が足りなかった気がする。
    • 焼きなまし法のマスの状態遷移の調整（開始5時間経過あたり）で、"#TD"はいらないということに気づく。ここで、TD#がなくなったことで問題の条件が大きくかわったので、高速化できる要素等がないか改めて考えるべき。今回の場合、TD#がなくなったことにより、命令Sはマスが.LRどれでも直進1歩になったので、マス変更の影響がなくなる。
  • 2Dフィールドで、何かを動かすというのは、マラソンマッチでは定番。それなのに、経路を圧縮するのを思いつかないのは、ダメ。
  • せめて焼きなましの温度調整は、自動化したほうが良かった気がする。30ケースで軽いからと、自動化しなかった。
  • 一部ソースコードが大変に汚い（ムダなif文など）。コード汚いと、基本遅いし、また、いろいろ試すのをためらう原因になるので、ちゃんと書きましょう。

解法

マスを'..LR'の割合で遷移させる焼きなまし法。10万ループぐらい。5度→0度で線形変化。評価関数はスコアのまま。

やったこと

  • 変更マスを通ったロボットだけ、経路を更新する。
  • ロボット経路を保存して、ロボットの途中位置から計算
  • マスは1次元配列で持つ
  • 遷移状態の調整。TD#を使わない。
  • 焼きなまし、変化スコアが悪くなったら計算途中早期打ち切り。
    • わりと重要テクニックで。これで焼きなまし回数が2万→10万ぐらいまで増え、13万到達。

やったけどボツ

  • 中央付近にLR少なめ
  • 中央付近はあまり変えない
  • ロボット0の箇所の評価点を、最初は高めに
  • 初期盤面を、高スコアのときの割合の'L''R'に合わせて配置

やらずにボツ

  • ロボットが4個・5個重なるケースにわずかに加点。そもそも、初期状態でも、ほぼ4,5がなかった。でも、やって損はなかったのでは。
  • 'S'の数の偶奇でロボットを分ける（壁にぶつかると無意味）

気づかなかったこと

  • 移動コマンドの圧縮。
  • 変更マスを通り、回転するロボットだけの経路を更新する。（上記の説明）
  • 初期L盤面。


  • kimiyukiさんの解答によると、「中央にDで縦棒を引いて土管のようなものを作るとLが実質小さくなるので速い」。kimiyukiさん、面白い形状をつくった改善が得意な印象があります。

最重要

復習しないとムダ。復習しないとムダ。復習しないとムダ。