🐸

[鉄則A22] Sugoroku (配るDP)

2024/04/04に公開

Ruby

すごろくのイメージで「配るDP」を学べる問題。

例1で問題を理解する

すごろくで 7 つのマスがある。

	1 (START)	2	3	4	5	6	7 (GOAL)
A	2	4	4	7	6	7		+100円
B	3	5	6	7	7	7		+150円

たとえば 1 のマスで A を選択すると 100 円を得て 2 のマスまで進む。B なら 150 円を得て 3 のマスに進む。ゴール地点での金を最大にしたい。

これはひと目ではわからないが、2 5 6 7 と進んだときに 100 + 150 + 100 + 150 で最大の 500 円になる。

注意点

A, B の要素は N - 1 個しかない。ゴール地点からはどこにも進まないため。

解説の模範解答 (AC)

97 ms

N = gets.to_i                             # => 7
A = gets.split.collect(&:to_i)            # => [2, 4, 4, 7, 6, 7]
B = gets.split.collect(&:to_i)            # => [3, 5, 6, 7, 7, 7]
A.unshift(nil)
B.unshift(nil)
dp = Array.new(N.next, -Float::INFINITY)
dp[1] = 0
(1...N).each do |i|
  dp[A[i]] = [dp[A[i]], dp[i] + 100].max  # => 100, 200, 250, 350, 350, 450
  dp[B[i]] = [dp[B[i]], dp[i] + 150].max  # => 150, 250, 300, 400, 400, 500
end
p dp[N]                                   # => 500

今を基点に未来を複数更新する。問題がすごろくなのでわりとイメージしやすい。

また問題文に合わせて 1-based インデックスになっている。dp[0] は貰うDPの要領で空けているわけではない。

リファクタリング後 (AC)

127 ms

N = gets.to_i                               # => 7
A = gets.split.collect { |e| e.to_i.pred }  # => [1, 3, 3, 6, 5, 6]
B = gets.split.collect { |e| e.to_i.pred }  # => [2, 4, 5, 6, 6, 6]
dp = Array.new(N, -Float::INFINITY)
dp[0] = 0
N.pred.times do |i|
  dp[A[i]] = [dp[A[i]], dp[i] + 100].max    # => 100, 200, 250, 350, 350, 450
  dp[B[i]] = [dp[B[i]], dp[i] + 150].max    # => 150, 250, 300, 400, 400, 500
end
p dp[N.pred]                                # => 500

配るDPでは過去を参照しないので 0-based インデックスにしやすい。これで一つずれている気持ち悪さを解消できる。

例1で問題を理解する

注意点

解説の模範解答 (AC)

リファクタリング後 (AC)

Discussion