トヨタ自動車プログラミングコンテスト2024#6（AtCoder Heuristic Contest 034) 解法

解法

最小費用流 (7.9G)

実はこの問題、トラックの移動経路を固定すると、最適解を求めることが出来ます。最適解というのは、$h_{ij} < 0$なのに更に掘り出すケース、あるいはトラックが複数回同じ頂点を通るケース等も対応した上での厳密な最適解です。

うまくグラフを作って最小費用流を流すのですが、きりさんのこのtweetの図がわかりやすいです。

文章で書くと、トラックの移動経路の頂点数を $M$ として、

  • 移動経路に対応した頂点が $M$ 個
  • グリッドのマス目に対応した頂点が $N^{2}$ 個
  • 始点 $S$, 終点 $T$

で計 $M + N^{2} + 2$ 頂点のグラフを作ります。そして、次のように辺を張ります。

  • 各グリッドのマス目$(i, j)$ の頂点について、$h_{ij} > 0$ ならば $S$ から (cap, cost) = $(h_{ij}, 0)$ の辺を張る
  • 各グリッドのマス目$(i, j)$ の頂点について、$h_{ij} < 0$ ならば $T$ へ $(-h_{ij}, 0)$ の辺を張る
  • 各移動経路の頂点について、対応するグリッドのマス目の頂点との間に、$(\infty, 1)$ の辺を双方向に張る
  • 各 $i = 1, 2, \cdots, M - 1$について、 $i$ 番目の移動経路の頂点から $i + 1$ 番目の移動経路の頂点へ $(\infty, 1)$ の辺を張る

実際に、このグラフで $S$ から $T$ に最小費用最大流を流すと、

  • 移動経路の頂点とグリッドのマス目の頂点の間の辺の流量が 積み込み/積み下ろし の量に対応し、
  • 移動経路の頂点間の辺の流量がトラックの運ぶ量に対応する

ことがわかります。

トラックの移動経路としてなにを取るかですが、次の図のように(ジグザグ + 向きを変えたジグザグ)で盤面を二回ずつ通るようなwalkを採用すると7.9G程度のスコアを取ることが出来ます。

実装例: Submission #54667347 - Toyota Programming Contest 2024#6（AtCoder Heuristic Contest 034）

ちなみにこの最小費用流の嬉しいポイントとして、あらゆる解法に対して最後にやって損しない後処理として機能します。つまり実装しても絶対無駄にならないです。

山登り(9.4G)

さらなる改善のためには、よりよい移動経路を探す必要があります。現状だとそもそも完全に経路を決め打ってしまっているので、改善の余地はありそうです。

先述の解法を動かしてみると、運搬コストについてはかなりよさそうで、トラックの移動コスト $100 \times (M - 1)$ の方に改善幅がありそうな気持ちになります。よって、トラックの移動距離を短くするような遷移で山登りをすることを考えます。

この思想を元に、「現在の移動経路について、$i$ 番目の頂点と $i + 3$ 番目の頂点が隣接していたならば、$i + 1$ 番目と $i + 2$ 番目の頂点を削除する」という遷移を考えます。これは上記のジグザグにおいて、曲がる部分をちょっとショートカットして短くする遷移です。

実際にこの遷移を書くと、とんでもなく強力なことがわかります。なんと時間いっぱい山登りするだけで9.4G程度のスコアが取れます。

実装例: Submission #54668251 - Toyota Programming Contest 2024#6（AtCoder Heuristic Contest 034）

なお、更なる改善として自然なのは焼きなましですが、ここで最小費用流(=スコア関数)の速度が問題になります。seed 0で、AC Libraryだと600 ~ 700回程度、後述の強力最小費用流ライブラリを使っても1500回程度しか最小費用流が流せなかったので、焼きなましは厳しかったです。うまくやればこの程度の遷移回数でもなんとかなるんでしょうか？

さらなる改善(9.5G)

コンテスト中に9.48G, 後に9.53Gまで伸ばしましたが、正直もう本質的な改善は行っておらず、泥臭いことをしました。

  • より高速な最小費用流を使う
    • AC LibraryはPrimal-Dual法の実装としてそれなりに速いものになっていると思いますが、そもそも最小費用流に対してはNetwork Simplex / Cost Scalingなど高速なアルゴリズムが色々あります。LEMON (C++ library) - Wikipedia がC++の実装として有名で、実際にNetwork Simplexを使うと3倍程度は速くなるようです。
  • 多点スタート
    • 高速な最小費用流を使うと実行時間に余裕が出来るので多点スタートをするとスコアが上がります。9.53Gの提出ではジグザグの向きが2通り * 2回ずつ 375ms(=計1500ms)山登り -> 一番良かったやつを更に400ms山登り
  • 雰囲気で適当に山登りの遷移を足して、仕上げの山登りで使用