search
LoginSignup
0

More than 1 year has passed since last update.

posted at

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 に詳しくなった

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