ABC 240の問題を解説
Ruby で解説している記事が少なかったので、解説していきます。
今回解説するのは以下の問題です。
解答
自分が作成した解答は以下のコードになります。
一つ一つ解説していきます
N,X=gets.split.map(&:to_i)
a=[]
b=[]
N.times{
aa,bb=gets.split.map(&:to_i)
a << aa
b << bb
}
dp=Array.new(N+1){Array.new(X+1,false)}
dp[0][0]=true
# iは 0~N-1 jは 0~X もらう dp
for i in (0..N-1) do
for j in (0..X) do
next if dp[i][j]==false
dp[i+1][j+a[i]]=true
dp[i+1][j+b[i]]=true
end
end
puts dp[N][X] ? "Yes" : "No"方針
今回はもらう DP で解いていきます。
また、N 回のジャンプで X に到達できるかどうか調べるにあたって、N+1行X+1列のマスを考えます。
これをdp=Array.new(N+1){Array.new(X+1,false)}で表しています。
初期値はdp[0][0]=trueとします
残りは、マスを一つ一つ調べていって、trueなマスがあったら、その次の行の同じマスにa[i],b[i]を足し、trueにするだけです。
具体的には以下の部分です
for i in (0..N-1) do
for j in (0..X) do
next if dp[i][j]==false
dp[i+1][j+a[i]]=true
dp[i+1][j+b[i]]=true
end
endそして調べたい地点Xがtrueかどうか確認すればこの問題は完了です！
puts dp[N][X] ? "Yes" : "No"解説は以上になります。
分かりにくい、または間違っているところあれば連絡いただければと思います。
連絡先
何か連絡をしたい際は以下 SNS、メールでお願いいたします。
Twitter: https://twitter.com/naka_ryo_z