🐢
[鉄則A35] Game 4
問題のイメージにひっぱられると永遠に解けないDP問題。
問題を要約する
- N 段のピラミッドの底辺部分に N 個の数字が書いてある
- 頂上にある駒を左下か右下に動かしながら底辺の数字を選択する
- 先手は最大、後手は最小の数字を選択したい
例1で問題を理解する
底辺には 20, 10, 30, 40 が並んでいるので、
- 先手は駒を 40 に向かわせたいので右下に動かした
- 後手はそれを阻止するために駒を左下に動かした
- 先手の選択肢は 10, 30 になって右下に動かした
となって最後に 30 を選択する。
まちがった考え方
頂上から下に駒を動かしていくのをイメージしてしまうとまったく解けない。
正しい考え方
駒のことなんか忘れて下から頂上に数字を持って上がる。
- 3段目の先手は左下と右下の大きい方を持ち上げる
- 2段目の後手は左下と右下の小さい方を持ち上げる
- 1段目の先手は左下と右下の大きい方を持ち上げる
すると不思議なことに頂上に 30 がある。
解説の模範解答 (AC)
230 ms
N = gets.to_i # => 4
A = gets.split.collect(&:to_i) # => [20, 10, 30, 40]
dp = Array.new(N) { [] }
dp[N - 1] = A
(N - 2).downto(0) do |y|
dir = y.odd? ? :min : :max
y.next.times do |x| # 段数と横のブロック数は同じため
dp[y][x] = [
dp[y + 1][x], # 左下
dp[y + 1][x + 1], # 右下
].send(dir)
end
end
dp # => [[30], [20, 30], [20, 30, 40], [20, 10, 30, 40]]
p dp[0][0] # => 30
Discussion