はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Typical DP Contest A - コンテスト
Difficulty: ---

今回のテーマ、動的計画法

問題自体は動的計画法の基本だと思われます。

Hash#keys

ruby.rb

gets
p = gets.split.map(&:to_i)
dp = Hash.new(0)
dp[0] = 1
p.each do |x|
  dp.keys.each do |y|
    dp[x + y] = 1
  end
end
puts dp.size

やっていることは、@kakudaisuke さんの AtCoder Typical DP ContestのA - コンテストを絵で理解してみたい（PHP）の通りです。

Hash#each_key --失敗--

ruby.rb

gets
p = gets.split.map(&:to_i)
dp = Hash.new(0)
dp[0] = 1
p.each do |x|
  dp.each_key do |y|
    dp[x + y] = 1
  end
end
puts dp.size

error.rb

can't add a new key into hash during iteration (RuntimeError)

反復中にハッシュに新しいキーを追加できません
ああ、似ているけどkeys.eachとeach_keyは違うのですね。

Array コピー

ruby.rb

gets
p = gets.split.map(&:to_i)
dp = Array.new(p.sum.next, 0)
dp[0] = 1
p.each do |x|
  dt = dp.dup
  dp.each_index do |i|
    next if dt[i].zero?
    dp[x + i] = 1
  end
end
puts dp.count(1)

配列の場合、代入はできるのですが、正解を得るにはclone又はdupにて配列をコピーする必要があります。

Array 後ろから

ruby.rb

gets
p = gets.split.map(&:to_i)
dp = Array.new(p.sum.next, 0)
dp[0] = 1
p.each do |x|
  p.sum.downto(0) do |i|
    next if dp[i].zero?
    dp[x + i] = 1
  end
end
puts dp.count(1)

downtoやeach_indexを使用し、後ろから探索すると、配列のコピーが不要となります。

まとめ

Typical DP A を解いた
Ruby に詳しくなった