HACK TO THE FUTURE 2020予選
HTTF2020予選に参加しました。結果は22位(4963718点)でした。
① 正の得点(48047点)
Text(cat)
0
② 拡張Dijkstra解法(4961249点)
(座標, 向き)でグラフを拡張して、直進はコスト0, 方向転換はコスト1のedgeを張って、拡張Dijkstraをする。則ち、「このマスでこっちを向いているロボットがいるとき、いくつの方向案内を新たに置けばゴールに着けるか」を求める。
コストが正であるロボットのうち、最小のコストを持つロボットについて、ゴールに着けるように方向案内を置く(そのようなロボットが複数存在する場合は、インデックスで最小のロボットを採用する)
再び拡張Dijkstraを行う。これを、(ゴールまで到達する道が存在するような)全てのロボットがゴール可能になるまで繰り返す。
実行時間は約100ms
③ 拡張Dijkstra + ロボットのインデックスシャッフル(4963153点)
②はロボットのインデックスに応じて結果が変わる。
Time Limit 一杯まで、毎回ロボットのインデックスをシャッフルして②を繰り返す。
④ 拡張Dijkstra + ロボットのインデックスシャッフル + 不要な方向案内削除(4963718点)
最後に不要な方向案内を削除する。
その他試したけど無意味だったこと
コストが同率な複数ロボットが存在するとき、ゴールまでの距離が最小(最大)のロボットを採用する。
スコア下がった
ロボットのインデックス順で焼きなまし
一回のシミュレーションで100ms掛かるのに焼きなまし、意味ある？無いね
試すべきだったこと
Dijkstraの代わりに0-1BFSで高速化
コスト1種類しか使ってないので当然0-1BFSでok
これ気付かなかったの酷すぎる...「本職がマラソンじゃなくてアルゴだから」とか言い訳も出来ないレベルの失態ですね...
非通過のマスを通過するときボーナス
上位陣のコードをいくつか実行して確かめたのですが、自分のコードと上位陣のコードを比較したところ、Bの差はほぼ無く、Cの差で負けている状態でした。
Cを高める上手い方法が分からなかったので殆ど無視してしまったのですが、こうすれば良かったのか...
おわり
ほ゛ん゛せ゛ん゛い゛き゛た゛か゛っ゛た゛
