競プロ日記008: MM141に参加しました！

MM141

TopCoderマラソンマッチ(MM141)に参加しました．この日記を書いているのが10月28日で公式な結果はまだ出ていませんが，PROVISIONAL RANKは25位，最終順位は23位でした．

今回からマラソン参加時に簡単な日記を書くようにしてみたので，今後の自分用と，これからマラソンマッチを始める人にとって少しでも参考になれば良いかなーと思って書き残しておきます．

10/20(Thu)

予定通り午前2時に起きて，サンプルコードとテスターのダウンロードを手早く済ませました．

不具合でページが消えたり一時的に閉鎖されることがあるかもしれないので，問題ページは念のためスクショ．

その後問題をちょっと読んで寝て，日中は普通に仕事をしました．適当に信号を切り替えるだけならすぐできますが，先々のこと(たぶんシミュレーションが必要)を考えて，最初の段階でできるだけ丁寧に書いておこうと，信号切り替え→実際に車を動かす→入力を取る→整合性チェックを厳しめにすることにしました．しかし仕事の後にコードを書いてみるものの眠すぎてめちゃくちゃなコードを書いてしまった結果，次の日の作業が無駄なデバッグ祭りになりました．眠いときはおとなしく寝た方がマシですね．とはいえ，最初にきちんとやっておくことはとても重要で，方向性は正しい(はず)です．

10/21(Fri)

前日に書いたコードを修正して動かしての繰り返し．バグは大体取れたはずなのにいくつかのケースでスコアが-1になってしまいました(assert入れまくってるので異常終了)．ビジュアライザで見てみたら，

ナニコレ😰…とかなり焦ったのだけど，これ(道がつながっている)は明らかにテストケースがおかしいんじゃないかと思ってフォーラムを確認してみたら修正版のテスターが公開されていました．初日に張り切ってテスターをダウンロードしたのは良いけど，初期のバージョンは修正が入るかもしれないので注意しないとですね…．その後テスターを差し替えて1000ケースほど試したらすべて正のスコアが得られたので，満足して就寝．この日はおしまい．

10/22(Sat)

最低限の実装を一通り終えて提出するとスコアは78点くらいで12位，悪くなさそうです．いくらか点は上がるビジョンがあるので安心してこの日の業務を行うことができました．この時点では，グリッド上にあるすべての車について，とにかく前に進むだけです．信号に引っかかって動けなくなれば信号を切り替えるというだけ．それでもそこそこのスコアが出るので，これってめっちゃいい感じじゃね？と思ったもののそこからスコアを挙げる方法がよくわからず．とりあえず前に進める車に優先順位を与えることから取り掛かろうと日曜日の方針を決めて寝ることにしました．

10/23(Sun)

比較的時間はあるので，家族とのんびり過ごしながら何か思いついたら実装して確認というのを何度も繰り返していました．しかしいろいろやっても推定1～2点くらいしか上がらなさそうなので，100ケースくらいをビジュアライザでチェックしたところ，

見事に詰まっていますね！まあ何の対策もしていないのでそりゃそうか，ということで進んださらに1マス前に他の車がいる(あるいは来る)場合は一旦停止することにしました．

これで幾分マシになりましたが根本的な問題は解決せず．かといって賢いアイデアもないので，1マス先だけじゃなく2マス先も見るようにしてみました．

これでもう少しスコアが上がったので一旦提出すると87点くらい．まあよしということでこの日は終わり．

10/24(Mon)

朝から予定が詰まっていてほとんどノータッチでしたが，いくつかのseedで極端に点が低いことがわかったので残りの時間はグリッドロック対策を行うことに絞り込みました．

10/25(Tue)

調査の結果，やはり早い段階でグリッドロックしていることが確認できました．まずはグリッドロックを検出できるようにしなければいけないということで，それだけ頑張りました．

夜中まで頑張って，「次のターンでグリッドロックが発生するよ！」というのを見つける処理を実装できました．この状態になったら上手く調整して渋滞を回避しないといけないのだけど，残り時間を考えるとバグらせずに組み上げる自信がなかったので，渋滞に関与している車をランダムに停車させて渋滞を回避できるかを何回か(10回)試してみる処理にしました．完全に渋滞を防げるわけではないけどだいぶマシになりました．これで最終日に時間がなくても提出できる状態までもっていけそう！

10/26(Wed)

最終日．普段は高速化とかパラメータの調整くらいしかできそうなことがないけど，今回は割と実装げーな感じでやることが無限にある感じでいつもと違う充実感がありました．残り時間と相談しつつ，できそうなことだけ進める．この日やったのは，まだ動く余地があるのに止まってしまうことをできるだけなくすように，取り除けそうな条件式を取ってはバグって取ってはバグって，じんわりスコアアップしていきました．渋滞が発生したら一時的に車を出現をブロックする処理を加えてみたら，渋滞が起こりやすいケースではある程度機能するもののそうでない場合はスコアが下がってしまってトータルではそんな感じだったので，無理やりコントロールするのは断念しました．

23時くらいに完成して提出し，お疲れ様でしたーと終わるつもりだったのですが，不要なコードを削除していたら削除前とスコアが変わってしまったので，「絶対バグあるやんこれ😱」ということで泣きながらデバッグしました．で，提出できたのが1時57分と超ギリギリ．まあ何とか間に合いました．スコアが1.5点くらい増えたので，もしかしたら2～3ケースWAを出していたのかも．

というわけで，やりたいことがすべて実現できたわけではないけれども何とか形にできました．