Ruby で解く AtCoder ABC057 C 動的計画法

はじめに

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

今回のお題

AtCoder Beginner Contest C - Digits in Multiplication
Difficulty: 904

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

この問題は、以前に Ruby と Python で解く AtCoder ABC057 C 素因数分解 ビット全探索 で解いております。

今回、動的計画法で解くことにより、実行時間が大幅に縮小したので投稿します。

ビット全検索

ruby.rb

require 'prime'

n = gets.to_i
h = n.prime_division
p = []
h.each do |k, v|
  v.times do
    p << k
  end
end
min = Float::INFINITY
0.upto(2**p.size - 1) do |bit|
  a = 1
  p.size.times do |i|
    a *= p[i] if bit[i].zero?
  end
  min = [a, n / a].max if min > [a, n / a].max
end
puts min.to_s.size

bit.rb

0.upto(2**p.size - 1) do |bit|
  # 処理
end

ここが、ビット全検索の部分になります。

動的計画法

ruby.rb

require 'prime'

n = gets.to_i
if n == 1
  puts 1
  exit
end
p = n.prime_division
dp = Hash.new(0)
dp[1] = 1
min = Float::INFINITY
p.each do |k, v|
  v.times do
    dp.keys.each do |u|
      dp[k * u] = 1
      tmin = [(k * u).to_s.size, (n / (k * u)).to_s.size].max
      min = tmin if min > tmin
    end
  end
end
puts min

動的計画法の処理内容については、Ruby の Hash における keys.each と each_key の違い を参照願います。

	ビット全検索	動的計画法
コード長 (Byte)	318	344
実行時間 (ms)	1504	69
メモリ (KB)	14416	14468

実行時間が1504->69と、大幅に縮小。

どうして早いのか

ビット全検索の場合、その都度計算される（上記ソースですと乗算）

1	=	1
1 * 2	=	2
1 * 2 * 3	=	6
1 * 2 * 3 * 5	=	30

動的計画法の場合、前回の計算結果を使用する

1	=	1
1 * 2	=	2
2 * 3	=	6
6 * 5	=	30

よって、計算コストが低くなります。

まとめ

• ABC 057 C を解いた
• Ruby に詳しくなった