読者です 読者をやめる 読者になる 読者になる

Topcoder Open 2016 Marathon Match(Round 3)の参加日記

C# プログラミングコンテスト マラソンマッチ Topcoder

制約が多くて面倒な問題だった。そのせいか、レート中位~下位の参加者がずいぶん少なかった。
結果は暫定62位/101人の定位置。

問題概要

  • 長さ1の正方形セル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


方針

  1. Dijkstraでアイテム・ターゲット・エッジセル間の距離を求める
  2. Dijkstraの結果を使い、アイテムとターゲットでTSP(ビームサーチ)
  3. TSP結果から有効解を作成(経路復元)
  4. 有効解を改善(貪欲+焼きなまし)


上位との比較

  • 全体的な方針は一緒
  • TS部分で大きな差がついている
  • TSは焼きなましの人と、2optなどTSP特有のアルゴリズムの人がいる
  • Dijkstraも、単純なセル間ではなくセルをさらに分割してる人もいた


反省
TSP部分で大きなスコア差が付いている。TSPがイマイチなのは気づいていたが、それより4の改善部分に時間を使ってしまった。
目についた部分を適当に改善するのではなく、どこに手を付けるべきかまず分析するべきだった。