HACK TO THE FUTURE 2019予選 参加記
コンテストページはこちら
HACK TO THE FUTURE 2019予選 - AtCoder
今回は初めてのマラソンマッチでした。慣れないうえに知識もないので苦労しましたが、それなりに楽しんでできましたし、何より次に繋がりそうな収穫を得られたのでよかったです。
やったこと
ステップ1 最低限の提出
まず、とりあえず正の得点を得るため、外周が壁、それ以外は通常マスを出力するコードを提出。80940点取れました。
提出コード - https://beta.atcoder.jp/contests/future-contest-2019-qual/submissions/3572739
ステップ2 得点差を考える
次に、ロボットが
- 0体から1体になるとき +10点
- 1体から2体になるとき -7点
- 2体から3体になるとき -2点
- 3体から4体になるとき -1点
- そのほか 変動なし
なので、2体になるマスに壁を置いたら上手くいくのでは？と考えました。しかし、愚直なシミュレーションでは時間がかかり過ぎるうえ、高速化のテクを思いつかず・・・仕方なく、「すでにロボットがいるマスに今見ているロボットが着きそうになったら、そのマスは壁に変える。そのマスが中央の場合は直前にいたマスを変える。ただし、変えたことにより既に見たロボットがどこに行くかはシミュレーションしない」というコードを書きました。そのうえで、全て通常マスの場合と比較し、良い方を出力することで、81032点になりました。
提出コード - https://beta.atcoder.jp/contests/future-contest-2019-qual/submissions/3574080
先程と同様に考え、全てをシミュレーションし終えてから2体になるマスを壁に変える、というものも比較対象に入れたところ、若干得点を伸ばすことができ、81185点になりました。
提出コード - https://beta.atcoder.jp/contests/future-contest-2019-qual/submissions/3578147
ステップ3 3秒たっぷり使ってシミュレーション
ここから、「ある1つのマスを変更し、その結果得点が高くなれば変更を適用する」というのを繰り返せば高得点を得られるのではないかと考えました。しかし、#LRDT全部を試そうとすると時間が足りません。愚直なシミュレーションでは2種類を試すことが精一杯でした。5C2 = 10通りのコードを5分おきに提出するという荒業に出て、結局LとRの組の115583点が最高点でした。
提出コード - https://beta.atcoder.jp/contests/future-contest-2019-qual/submissions/3579097
その他、盤面を時間いっぱいXor shiftで形成したり、探索するマスを少なくして3種類以上ずつ試したりしてコンテスト時間終了。115583点で116位でした。
ステップ4 常に中央から上向きでスタートすることに着目する
終了後、Twitterや解説放送などで得た情報をもとに、初期盤面はRで埋め、真ん中に近い方から順番に空白、Lに置き換えてみるというコードを書きました。すると、121231点まで伸ばせました。これがいい理由は、端に寄って膠着しやすいロボットをぐるぐる回せる、ということらしいです。
提出コード - https://beta.atcoder.jp/contests/future-contest-2019-qual/submissions/3581448
ここまでが今の自分の理解できる範囲かなという感じです。その他、シミュレーションするのを変更したマスを通るロボットだけにすることや、更にその変更したマス以降のみシミュレーションすることで計算量を抑えられ、より多くのパターンを探索できるという情報も得られました。これをする実装力を身に着けたいところです。また、「山登り法」「焼きなまし法」というワードを拾ったので、これらについて勉強するのを今後の課題としたいと思います。
