search
LoginSignup
0
Help us understand the problem. What are the problem?

Ruby その2 Advent Calendar 2020 Day 6

posted at

updated at

Ruby の Hash における keys.each と each_key の違い

はじめに

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.eacheach_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)

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

まとめ

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0
Help us understand the problem. What are the problem?