7K12 blog

猫でも分かるアルゴリズム解説

GigaCode 2019 E - 車の乗り継ぎ

f:id:tkr987:20200208194237p:plain

https://atcoder.jp/contests/gigacode-2019/submissions/13239335

これでdif12Kなのか。天才しかいない。

  • 初期値は all(dp)=ldbl_max, dp[0]=0
  • 繰り返しは rep(i, 1, N+2) rep(j, 0, i)
  • 更新は dp[i] = min(dp[i], dp[j] + (ld)(car[i].x - car[j].x) / (ld)car[j].v);
  • 出力は dp[N+2]
  • f:id:tkr987:20200517002127p:plain

制約からDPっぽいという事までは凡人でも感じるとは思う。問題はDPの定義。DP[i]を車[i]の終点に着目して定義しようとすると実装が難しい。今回はX[i]から車が出発することからDP[i]をX[i]までの最善とする。X[i]でソートし、更新式は以下のようになる。

 dp[i] = min(dp[i], \{T_1, T_2, ..., T_{i-1} \});  ただしX_iで物理的に乗り換えられない車のTは無視する

ゴール地点に架空の車を追加するとコーディングしやすい。スタート地点の車とゴール地点の車も考慮してdp[N+2]の値が求める答えとなる。計算量は O(N^{2})だが、制約から処理できる。