きままにものづくり

日々の気付いたことなんかを書いてます。

ARC019 C問題

問題


C: 最後の森 - AtCoder Regular Contest #019 | AtCoder

解法

スタート地点からほこらまでの最短距離、ほこらからゴール地点までの最短距離を求めることで答えが求まる。
途中の敵の数を減らすために、経由地点xを追加し、
スタート->x->ほこら->x->ゴール
という順序ですすむようにする。
スタート、ほこら、ゴールからそれぞれBSFで最短距離を計算することで時間内に計算することができる。
経由地点xに敵がいる場合は、3つ余分に数えているのでその分を考慮する。

計算量

O(RCK)

コード


補足

動的計画法を用いて、dp[h][k][r][c]
h:ほこらを通ったかどうか
k:敵を倒した回数
r:R
c:C
とした場合メモ化により一見O(KRC)で計算できるように見えるが、あるマスでの最小値を求めるための更新が必要となるためO(KRC)とはならずにTLEする。

広告を非表示にする