Ruby と Python で解く AtCoder ABC153 E 動的計画法

はじめに

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

今回のお題

AtCoder Beginner Contest E - Crested Ibis vs Monster
Difficulty: 1009

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

いわゆる典型的な動的計画法の問題です。
トキがモンスターに勝つまでに消耗する魔力の合計の最小値を求めます。
但し、モンスターの体力を0以下にするということで、0ジャストでなくてもいい点に少しだけ注意します。

Ruby

ruby.rb

h, n = gets.split.map(&:to_i)
a = Array.new(n){gets.split.map(&:to_i)}
dp = Array.new(h + 1, Float::INFINITY)
dp[0] = 0
h.next.times do |i|
  a.each do |x, y|
    if i + x < h && dp[i + x] > dp[i] + y
      dp[i + x] = dp[i] + y
    elsif i + x >= h && dp[h] > dp[i] + y
      dp[h] = dp[i] + y
    end
  end
end
puts dp[h]

ruby.rb

    if i + x < h && dp[i + x] > dp[i] + y
      dp[i + x] = dp[i] + y
    elsif i + x >= h && dp[h] > dp[i] + y
      dp[h] = dp[i] + y
    end

elsif i + x >= hのところで、モンスターの体力が0以下になったときの処理としてdp[h]に固定しています。

Python

pypy.py

from sys import stdin, maxsize

def main():
    input = stdin.readline

    h, n = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    dp = [maxsize] * (h + 1)
    dp[0] = 0
    for i in range(h + 1):
        for x, y in a:
            if i + x < h and dp[i + x] > dp[i] + y:
                dp[i + x] = dp[i] + y
            elif i + x >= h and dp[h] > dp[i] + y:
                dp[h] = dp[i] + y
    print(dp[h])
main()

PyPy の方でないとTLEになります。

	Ruby	Python	PyPy
コード長 (Byte)	336	476	476
実行時間 (ms)	1630	TLE	399
メモリ (KB)	2044	3616	41452

まとめ

• ABC 153 E を解いた
• Ruby に詳しくなった
• Python に詳しくなった