Topcoder Open 2016 Marathon Match(Round 3)の参加日記
制約が多くて面倒な問題だった。そのせいか、レート中位~下位の参加者がずいぶん少なかった。
結果は暫定62位/101人の定位置。
問題概要
- 長さ１の正方形セルSxS個で構成されるマップがある
- 各セルはタイプ（0~9）が設定されている
- マップ上にはN個のアイテムとN個のターゲットがある
- アイテムの近く（距離10^-3以内）に止まると、該当アイテムを拾う
- ターゲットの近くで止まると、持っているアイテムを落とす
- 1つのターゲットに落とすのは1つのアイテム
- 持てるアイテムの最大値はcapacityで与えられる
- すべてのアイテムをターゲットに落とさなければならない
- スタート地点はマップの外周から距離10^-3以内ならどこでもよい
- このとき、なるべく小さいコストで全アイテムをターゲットに落とすのが目的
- コストは、セルタイプx移動距離。タイプの違うセルをまたぐときは、さらにタイプ差の二乗が可算される
- 1回のステップでは、1つ以内のセルしかまたげない
- セルボーダーから距離10^-3以内には止まってはならない。
- ステップ間は10^-3以上の距離をおくこと
- S:10~50、タイプ数2~10、アイテム数:5~S*S/10、capacity:1~10
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16704&pm=14283
方針
- Dijkstraでアイテム・ターゲット・エッジセル間の距離を求める
- Dijkstraの結果を使い、アイテムとターゲットでTSP（ビームサーチ）
- TSP結果から有効解を作成（経路復元）
- 有効解を改善（貪欲＋焼きなまし）
上位との比較
- 全体的な方針は一緒
- TS部分で大きな差がついている
- TSは焼きなましの人と、2optなどTSP特有のアルゴリズムの人がいる
- Dijkstraも、単純なセル間ではなくセルをさらに分割してる人もいた
反省
TSP部分で大きなスコア差が付いている。TSPがイマイチなのは気づいていたが、それより4の改善部分に時間を使ってしまった。
目についた部分を適当に改善するのではなく、どこに手を付けるべきかまず分析するべきだった。
