Ruby と Python で解く AtCoder ABC178 D 動的計画法

はじめに

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

今回のお題

AtCoder Beginner Contest D - Redistribution
Difficulty: 830

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

いわゆる典型的な動的計画法の問題です。
前の記事 - Qiita で取り上げました、AtCoder Beginner Contest E - Crested Ibis vs Monster では、目標値を超えてた場合もケアしないといけませんが、今回はジャストでよいので、その分少し簡単です。

Ruby

ruby.rb

s = gets.to_i
dp = Array.new(s.next, 0)
dp[0] = 1
s.times do |i|
  next if dp[i].zero?
  3.upto(s) do |x|
    if i + x <= s
      dp[i + x] += dp[i]
      dp[i + x] %= 1000000007
    else
      break
    end
  end
end
puts dp[s]

ruby.rb

    if i + x <= s
      dp[i + x] += dp[i]
      dp[i + x] %= 1000000007
    else
      break
    end

今回はジャストでよいので、i + x <= sについてのみdpを加算します。

Python

python.py

from sys import stdin

def main():
    input = stdin.readline

    s = int(input())
    dp = [0] * (s + 1)
    dp[0] = 1
    for i in range(s):
        if dp[i] == 0:
            continue
        for x in range(3, s + 1):
            if i + x <= s:
                dp[i + x] += dp[i]
                dp[i + x] %= 1000000007
            else:
                break
    print(dp[s])
main()

PyPy は凄く速いですね。

	Ruby	Python	PyPy
コード長 (Byte)	244	405	405
実行時間 (ms)	284	509	70
メモリ (KB)	14400	9060	64596

まとめ

• ABC 178 D を解いた
• Ruby に詳しくなった
• Python に詳しくなった

参照したサイト
Ruby と Python で解く AtCoder ABC153 E 動的計画法 - Qiita