Ruby で解く AtCoder ABC 128 C 動的計画法

はじめに

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

今回のお題

AtCoder Beginner Contest 128 C - Switches
Difficulty: 805

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

この問題は、以前に Ruby と Perl と Java で解く AtCoder ABC 128 C で解いております。

今回、ビット全検索から動的計画法へ次の様に変換しました。

ビット全検索	動的計画法
入力	入力
-	dp配列生成
判定	判定
出力	出力
これにより、ビット全検索は動的計画法を特化したアルゴリズムであることが分かります。

ビット全検索

ruby.rb

n, m = gets.split.map(&:to_i)
k = m.times.map{ gets.split.map(&:to_i)[1..-1].map{ _1 - 1 } }
p = gets.split.map(&:to_i)
cnt = 0
(0..2**n - 1).each do |x|
  f = true
  k.each_with_index do |y, i|
    v = 0
    y.each do |z|
      v += 1 if x[z] == 1
    end
    if v % 2 != p[i]
      f = false
      break
    end
  end
  cnt += 1 if f
end
puts cnt

bit.rb

(0..2**n - 1).each do |x|

ここからが、ビット全検索の判定部分になります。詳細は、Ruby と Perl と Java で解く AtCoder ABC 128 C を参照願います。

動的計画法

ステップ１

step1.rb

# before
(0..2**n - 1).each do |x|
# after
dp = (0..2**n - 1).to_a
dp.each do |x|

まず、dp配列を準備します。dpの中は、[0, 1, 2, ..., 2**n - 1] といった単純な数列です。

ステップ２

step2.rb

a = n.times.map{ 2**_1 } # => ex. [1, 2, 4, 8, 16]

次に、配列aを準備します。この配列は、A - Frog 1 で言うところの足場 i+1 または i+2 へジャンプするの移動量 [1, 2] に相当します。

ステップ３

step3.rb

a = n.times.map{ 2**_1 }
dp = Array.new(2**n, 0)
a.each do |x|
  (2**n - 1).downto(1) do |i|
    break if i - x < 0
    dp[i] = dp[i - x] + x
  end
end # => ex. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]

配列aより dp配列を生成します。こちらの動的計画法 と同様の操作になります。

完成

dp.rb

n, m = gets.split.map(&:to_i)
k = m.times.map{ gets.split.map(&:to_i)[1..-1].map{ _1 - 1 } }
p = gets.split.map(&:to_i)
cnt = 0
a = n.times.map{ 2**_1 }
dp = Array.new(2**n, 0)
a.each do |x|
  (2**n - 1).downto(1) do |i|
    break if i - x < 0
    dp[i] = dp[i - x] + x
  end
end
dp.each do |x|
  f = true
  k.each_with_index do |y, i|
    v = 0
    y.each do |z|
      v += 1 if x[z] == 1
    end
    if v % 2 != p[i]
      f = false
      break
    end
  end
  cnt += 1 if f
end
puts cnt

実際の競技でビット全検索の問題を動的計画法で解く必要はないと思いますが、精進におけるビット全検索から動的計画法へのステップアップになればと思います。

まとめ

• ABC 128 C を解いた
• 動的計画法 に詳しくなった