Solving with Ruby and Python AtCoder ABC153 E Dynamic programming

Introduction

This theme

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

This theme, dynamic programming

It is a problem of so-called typical dynamic programming. Find the minimum total amount of magical power that Toki consumes before winning a monster. However, please note that it does not have to be 0 just by making the monster's physical strength 0 or less.

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

At ʻelsif i + x> = h, it is fixed to dp [h]as the processing when the monster's physical strength becomes0 or less`. 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()

If you are not *** PyPy ***, it will be TLE.

Ruby Python PyPy
Code length(Byte) 336 476 476
Execution time(ms) 1630 TLE 399
memory(KB) 2044 3616 41452

Summary

Recommended Posts

Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
Solving with Ruby, Perl, Java and Python AtCoder ABC 107 B String Manipulation
Solving with Ruby, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
Solving with Ruby and Python AtCoder ARC 059 C Least Squares
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solving with Ruby and Python AtCoder AISING2020 D Iterative Squares
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B
Solving with Ruby, Perl, Java and Python AtCoder diverta 2019 Programming Contest C String Manipulation
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Solving with Ruby AtCoder ABC110 C String Manipulation
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
Solving with Ruby, Perl, Java, and Python AtCoder ARC 098 C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
Programming with Python and Tkinter
Solve AtCoder ABC166 with python
AtCoder ABC 178 Python (A ~ E)
AtCoder ABC 176 Python (A ~ E)
Solve AtCoder ABC 186 with Python
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solving with Ruby and Python AtCoder CODE FESTIVAL 2016 qual C B Priority queue
[Python] Technique to reduce dimensions with DP (Dynamic Programming) [AtCoder]
Scraping with Node, Ruby and Python
Dynamic proxy with python, ruby, PHP
Solved AtCoder ABC 114 C-755 with Python3
Template AtCoder ABC 179 Python (A ~ E)
AtCoder ABC168 A case expression solved in Ruby and Python
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
Eating and comparing programming languages: Python and Ruby
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
Encrypt with Ruby (Rails) and decrypt with Python
Easy web scraping with Python and Ruby
Learn dynamic programming in Python (A ~ E)
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
AtCoder ABC130 D Cumulative Sum Binary Search Solved by Ruby and Python
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
How to enjoy programming with Minecraft (Ruby, Python)
Solving the Lorenz 96 model with Julia and Python
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Solving in Ruby, Perl, Java, and Python AtCoder ARC 066 C Iterative Squares Hash
Solve with Python [100 past questions that beginners and intermediates should solve] (053 --055 Dynamic programming: Others)
Solve AtCoder 167 with python
3. 3. AI programming with Python
Python programming with Atom
Python and Ruby split