🐸
[鉄則B16] Frog 1
A16 - Dungeon 1 の応用で移動コストが「移動元と移動先の差分の絶対値」になっている問題。
問題を要約する
- 移動コストは段差の絶対値
- 一つ飛び越えることができる
- ゴールまでの最小コストは？
例1のシミュレーション
スタート地点に近い方から最小コストを順に求めていくと、
| 地点 | 理由 | コスト |
|---|---|---|
| 1 | 1からスタートするので | 0 |
| 2 | 1からのみ移動できるので | 20 |
| 3 | 1からも2からも同じなので | 30 |
| 4 | 2から飛んだ方が速いので | 30 |
となり 1-2-4 ルートが最小コスト 30 になる。
実装 (AC)
68 ms
N = gets.to_i # => 4
H = gets.split.collect(&:to_i) # => [10, 30, 40, 20]
START = 0 # => 0
GOAL = N.pred # => 3
dp = []
dp[START] = 0 # => 0
dp[1] = (H[1] - H[0]).abs # => 20
(2...N).each do |i|
a = dp[i - 1] + (H[i] - H[i - 1]).abs # => 30, 50
b = dp[i - 2] + (H[i] - H[i - 2]).abs # => 30, 30
dp[i] = [a, b].min # => 30, 30
end
p dp[GOAL] # => 30
マジックナンバーだらけでいけてないが素直に実装するとこうなる。
リファクタリング後 (AC)
78 ms
N = gets.to_i # => 4
H = gets.split.collect(&:to_i) # => [10, 30, 40, 20]
START = 0 # => 0
GOAL = N.pred # => 3
STEPS = [1, 2]
dp = [START]
(1...N).each do |to|
dp[to] = STEPS.collect { |step|
from = to - step
if from >= 0
dp[from] + (H[to] - H[from]).abs
else
Float::INFINITY
end
}.min
end
p dp[GOAL] # => 30
ステップ数のハードコーディングを消すと負のインデックスで配列のお尻を参照する副作用も回避できるようになった。ただ、何をやっているのかひと目でわからなくなった。
同一問題
同じ考え方で解ける。
Discussion