🐸

[鉄則A16] Dungeon 1

2024/03/20に公開

Ruby

動的計画法の基礎が学べる問題。

問題を要約する

A には順番に移動するときのコストが並んでいる
B には1つ飛ばしで移動するときのコストが並んでいる
ゴールまでの最小コストは？

例1のシミュレーション

スタート地点に近い方から最小コストを順に求めていくと、

地点	理由	コスト
1	1からスタートするので	0
2	1からのみ移動できるので	2
3	1から飛んだ方が速いので	5
4	2から飛んだ方が速いので	5
5	4から歩いた方が速いので	8

となり 1-2-4-5 ルートが最小コスト 8 になる。

3 に移動するまでは 1-3 ルートが有望だと思われていたが、4 への移動も考慮すると 1-2-4 ルートが見直されたのがわかる。

実装 (AC)

N = gets.to_i                   # => 5
A = gets.split.collect(&:to_i)  # => [2, 4, 1, 3]
B = gets.split.collect(&:to_i)  # => [5, 3, 7]

A = [0, *A]                     # => [0, 2, 4, 1, 3]
B = A.take(2) + B               # => [0, 2, 5, 3, 7]

dp = Hash.new(0)
N.times do |i|
  a = dp[i - 1] + A[i]          # => 0, 2, 6, 6, 8
  b = dp[i - 2] + B[i]          # => 0, 2, 5, 5, 12
  dp[i] = [a, b].min            # => 0, 2, 5, 5, 8
end
dp                              # => {0=>0, 1=>2, 2=>5, 3=>5, 4=>8}
p dp[N.pred]                    # => 8

A と B はちょうど N 個になるように揃えると A[i] B[i] と書けてすっきりする。

dp の最初の二つは確定しているので三つめから計算してもいいのだけど、何か気持ちわるいので N 回ループを回している。しかし、そうすると dp が配列型の場合、負のインデックスが配列のお尻にアクセスしてしまうのがやっかいである。この場合に限っては nil を返してほしいのだけどそうはならない。そのためだけに modulo(N) するのもいまいちだ。

なので結局 Hash.new(0) とした。あっちを立てればこっちが立たずで腑に落ちない。あまり気にせず普通に三つめから計算する方がいいのだろうか。

累積和の応用？

この問題から B を外してみると、

N = gets.to_i                   # => 5
A = gets.split.collect(&:to_i)  # => [2, 4, 1, 3]

A = [0, *A]

dp = Hash.new(0)
N.times do |i|
  a = dp[i - 1] + A[i]          # => 0, 2, 6, 7, 10
  dp[i] = [a].min               # => 0, 2, 6, 7, 10
end
p dp[N.pred]                    # => 10

と、なってこれはたんに累積和を求めているだけに見える。つまり、この問題の解法は累積和の過程で「良い方を選択する」ように改造しただけのものと言えなくもない。

ダイクストラ法でも解ける

N = gets.to_i                   # => 5
A = gets.split.collect(&:to_i)  # => [2, 4, 1, 3]
B = gets.split.collect(&:to_i)  # => [5, 3, 7]

START = 0                       # => 0
GOAL  = N.pred                  # => 4

G = Array.new(N) { [] }
A.each.with_index { |e, i| G[i] << [i + 1, e] }
B.each.with_index { |e, i| G[i] << [i + 2, e] }
G                               # => [[[1, 2], [2, 5]], [[2, 4], [3, 3]], [[3, 1], [4, 7]], [[4, 3]], []]

d = Array.new(N, Float::INFINITY) # distance
heap = Heap.new { |e| d[e] }

d[START] = 0
heap << START

while from = heap.pop
  G[from].each do |to, cost|
    v = d[from] + cost
    if v < d[to]
      d[to] = v
      heap << to
    end
  end
end

p d[GOAL]                       # => 8

このように、この問題はダイクストラ法で解けるが、すべての辺が GOAL に向いている場合は、そこまで大袈裟にする必要がなかったと考えられる。