Skip to content

トヨタ自動車プログラミングコンテスト2024#6(AHC034)

問題概要

  • N * Nマスの土地があり、各マスは土砂が高さh_{i,j}(負もあり、全マスでの合計は0)になっている
  • ダンプカーを操作し、隣接マスへの移動、または、土砂をdだけ積む・下ろす、ことができる
    • 移動には積んでいる土砂の量+100のコストがかかり、土砂の積み下ろしも移動する土砂の量分のコストがかかる
  • すべてのマスで高さが0になるようなできるだけコストの少ない操作列を求めよ

時間

  • 4 時間

個人的メモ

  • 思うよりもスコアを高めるのが難しい
  • 解説放送で上位の解法について紹介されている
    • ルールベース
    • マスの訪問順焼きなまし
    • パス＋最小費用流

最小費用流解

  • https://twitter.com/kiri8128/status/1802392043072970938
  • https://yosupo.hatenablog.com/entry/2024/06/17/221003
  • 4隣接のグラフではなく、パスで考えて、sから正の頂点、負の頂点からt、パスの隣接、でグラフを作ると最小費用流で考えられる
  • しかし、そのままでは2回以上通る頂点での積み込み、積み下ろしの量がわからないため、パスの頂点とマスの頂点を分けて考え、パスの頂点とマスの頂点間をつなぐ
    • sから正のマスの頂点、負のマスの頂点からtは、容量∞コスト1の辺を張る
    • マスの頂点とパスの頂点間も容量∞コスト1の辺を張る
      • マス→パスの流量が積み込み量、パス→マスが積み下ろし量になる

解説

(50位まで&発言を見つけられた方のみ)