HTTF2020参戦記
HTTF2020に参加しました
全然ダメだったけど反省のために書きます。325/834位でした。
最小全域木(シュタイナー木)の構築みたいのをして4901556点でした。最短経路問題ってなんですか？
まともに最小全域木作ろうとすると実装ができなかったので、最初に塗り絵をしてから無駄な部分を消して、消しすぎてゴールできなくなったら方向案内を追加するみたいな解法になった。
時系列
開始直後
まだ家についてなくてスマホで問題を読みつつprint(0)を出した。36位だかだった。
48047点
~2時間
とりあえずJavaで書き始めた。
ゴールマスの隣にマスを置くだけのやつを出そうとするがREを連発する。(x-1)%nを(x-1+n)%nにしたら直った。そういやそうだった。
50403点
~2時間30分
うねうねと触手みたいのを伸ばして回収していく作戦にした。ゴールから連続した誘導路を伸ばしていって触手に触れたロボットは全部吸い込む感じ。
触手を伸ばす方向が謎なこととそもそも全部のロボットをゴールさせることが必須なことにようやく気づいたので方針転換した。
~3時間
ゴールから到達可能なマスに全て置くやつをやっと実装する。ゴールに向かって歩くような向きを求めるのは触手の時に作っておいたので方向案内を敷き詰めるだけだった。
4392988点(解説放送でこれだけで480満点くらいって言ってたような気もするが気のせいか？)
~5時間20分
バグり散らかしたり方針が迷走したりが一旦実装が完了し改善する。ロボットが一度でも通る場所全てに方向案内を置いた。それだけだと連結にならないのでゴールからBFS(操作単位でなくマス単位)して連結にした。
4773586点
~6時間
連続して→→→みたいのを置くのが無駄なので消した。曲がり角を間違って消すとゴールできなくなるのでバグと闘った。
4884346点
~7時間
ほとんどのロボットの上には方向路があるのでそれの削除と方向を変えて他の方向路を削除する山登りを考える。
山登り時の方向路の選択はランダムなので時間目一杯回るようにタイマーを実装、TLEしないか確認のために一旦提出する。連続した方向路できちんと消せてない部分を多少修正したのでスコアが伸びる。(本番中はなぜかスコアが伸びたと思ってた)
4901556点
~8時間(終了時刻)
バグらせて終わる
反省
多くの人が実装していたゴールあるいはロボットからのダイクストラでの構築がやはり筋がよかったと思う。一瞬考えたような気がしたけど計算が間に合わないような気がして止めてしまった。(ロボットからダイクストラするやつは100msくらいだったらしい)
筋がよかったところ悪かったところが種々あるのだけれど大きいのは三つ。
- 開始90分ほどまで気づかなかったやつで、ロボットを全部ゴールさせなければならないという点。計算式を見たら明らかなので最初に気づけるはずだった。
- 最後までダイクストラを試さなかった点。連結にするためにBFS(ダイクストラ)はしてはいたが、１マスしか進まないやつだったのでダメだった。直進と方向転換でやるとよかったらしい。これ実装うまいな。
- 方向案内を消すのは計算のコストが大きいが、ゴールへ向かう方向案内の追加は注目していないロボットへの影響はなく再計算の必要が無いという本質を見逃していた点。焼きなましやビームサーチを考えると方向案内の削除は悪手だと思う。
490万点にぎりぎり乗せるくらいしかできなかったかなしい(´･_･`)
