🐢
[鉄則B32] Game 5
必勝法を求める前問をリファクタリングする問題。
問題を理解する
前問では 2 パターンだったが、それが可変になっている。
前問のおさらい
N, A, B = gets.split.collect(&:to_i) # => [8, 2, 3]
dp = Array.new(N.next)
(0..N).each do |i|
case
when i >= A && dp[i - A] == :lose # 2 枚引いた状況に切り替えて負けならそれは相手の負けなので自分の勝ち
dp[i] = :win
when i >= B && dp[i - B] == :lose # 3 枚引いた状況に切り替えて負けならそれは相手の負けなので自分の勝ち
dp[i] = :win
else # どちらもだめなら自分は負ける
dp[i] = :lose
end
end
# 最初の8枚目の手番を得た先手の必勝
dp[N] # => :win
puts dp[N] == :win ? "First" : "Second"
選択肢を可変にした実装 (AC)
150 ms
N, K = gets.split.collect(&:to_i) # => [8, 2]
A = gets.split.collect(&:to_i) # => [2, 3]
dp = Array.new(N.next)
(0..N).each do |i|
if A.any? { |e| i >= e && dp[i - e] == :lose }
dp[i] = :win
else
dp[i] = :lose
end
end
# 最初の8枚目の手番を得た先手の必勝
dp[N] # => :win
puts dp[N] == :win ? "First" : "Second"
Discussion