Approach プログラムは、焼きなまし法を使いました。私も、提出して調整する焼きなまし法を使いました。

735e4(初AC解)
  • test_1 523395
    test_2 710000
    test_3 700000
    test_4 750000
    test_5 780106
    test_6 505273
    test_7 801633
    test_8 860000
    test_9 820000
    test_10 900000
  • 初期解 : 使うパーキングの数を最小にして入力された順に配置。
  • 時間 : 10秒
  • 近傍 :
    • 配達先の移動
    • 2つの配達先またはパーキングの交換
    • パーキングの変更
    • 2つの(パーキング+配達先)の交換
    • パーキングを出発してから戻ってくるまでの配達先の順番の2opt
      • 出発してから戻ってくるまでは、巡回セールスマン問題なので
  • 温度 : 100->0(線形)
  • 評価関数 : (制限時間内に配達した荷物の個数 * 10000.0)
     + (240 * 60.0 - 全ての荷物を配達し終えた時間 * 60.0)
     - (有効な解にならない要素の数 * 1e7)
    • "全ての荷物を配達し終えた時間" は、短いほうが良い解が見つかりやすいだろうと思って0以下でもそのままにしておいた。
    • "- (有効な解にならない要素の数 * 1e7)" は、ペナルティで有効な解を見つけやすくした。
  • 高速化 : してない。
    • 最大ケースでも60秒で3千万回評価できたので、近傍や評価関数のほうが重要かな~と思った。


755e4(best)
  • test_1 523276
    test_2 740013
    test_3 760124
    test_4 780008
    test_5 780063
    test_6 505402
    test_7 801789
    test_8 870081
    test_9 840016
    test_10 950004
  • 初期解 : 使うパーキングの数を最小+1にして入力された順に配置。
    • 1つ余裕をもって、いろんな形の解に変更できるようにした。(+30000点)
  • 時間 : 60秒(+60000点)
  • 近傍 :
    • 配達先の移動
    • 2つの配達先の交換
    • 3つの配達先の交換(+30000点)
    • 複数の連続するパーキングの変更
    • 2つの(パーキング+配達先)の交換
    • 配達先の順番の2opt
      • 同じパーキングを連続して使うのが良いと分かったので、幅を広くしてもよさそうだと思った。
  • 温度 : 150->0(線形)
  • 評価関数 : (制限時間内に配達した荷物の個数 * 10000.0)
     - (制限時間(制限時間が 0 のものは 240 を制限時間にする)に遅れた荷物の中で、遅れた時間の最小値 * 60.0)
     + 0.1 * (240 * 60.0 - 全ての荷物を配達し終えた時間 * 60.0)
     - (有効な解にならない要素の数 * 1e7)
    • "- (制限時間に遅れた荷物の中で、遅れた時間の最小値 * 60.0)" は、制限時間に間に合いやすくするため。(+50000点)
    • "+ 0.1 * (240 * 60.0 - 全ての荷物を配達し終えた時間 * 60.0)" の係数 0.1 は、上を優先するため。
  • 運 : +30000点
    • これで 752e4が安定して、753e4も普通に出ます。テストケースごとのベストスコアで 754e4 だったけど、運よく飛び越えて 755e4 が出てしまった。

  • ほとんど車両で移動しなかった。これでいいのか?台車が6km/h、車両が15km/h(ヤマトの車は確かに遅い)ならこんなものか?
    • ローカルで、配達先とパーキングを、道路上という設定を無視してランダムに配置して、距離にユークリッドを使って、パーキング間を瞬間移動できるようにしても、車両の移動はほとんど使われなかった。
    • ほとんど車両で移動しないは、同じパーキング間の距離が0なのと、そのパーキングから行き来する配達先が多くなって、スコアの差が大きくなるからだろうと思って、パーキングの変更の近傍の時だけ、温度を変えたり、スコアの差が小さくなるように定数を掛けたりしたら、解を見ると少しだけ車両で移動するようになったが、スコア的には良くなった感じはなかった。
  • ローカルで、雑にテストデータを作ると、有効な解が見つからないことも多くて、"制限時間に間に合ってない荷物を保持して、そこから選んで交換 移動させる近傍"が良かったけど、提出すると悪くなった。
  • "2つの配達先の交換" から "2つの近い配達先の交換" に変更しても良くなったと思うけど、"3つの配達先の交換" を追加したら、効果が分からなくなった。