Solving with Ruby and Python AtCoder ABC178 D Dynamic programming

Introduction

This theme

AtCoder Beginner Contest D - Redistribution Difficulty: 830

This theme, dynamic programming

It is a problem of so-called typical dynamic programming.

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

This time it's just fine, so add dp only for ʻi + x <= s`. 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 *** is really fast, isn't it?

Ruby Python PyPy
Code length(Byte) 244 405 405
Execution time(ms) 284 509 70
memory(KB) 14400 9060 64596

Summary

Referenced site

Recommended Posts

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 ABC153 E Dynamic programming
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
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
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solving with Ruby and Python AtCoder AISING2020 D Iterative Squares
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
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
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solving with Ruby and Python AtCoder ARC 059 C Least 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
Solve AtCoder ABC168 with python (A ~ D)
Solving with Ruby, Perl, Java and Python AtCoder diverta 2019 Programming Contest C String Manipulation
Solving with Ruby AtCoder ABC110 C String Manipulation
AtCoder ABC130 D Cumulative Sum Binary Search Solved by Ruby and Python
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
[Python] Dynamic programming TDPC D
AtCoder ABC 182 Python (A ~ D)
Solve AtCoder ABC 186 with Python
AtCoder ARC080 D simulation solved in Ruby and Python
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
Solve ABC166 A ~ D with Python
Solved AtCoder ABC 114 C-755 with Python3
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
Encrypt with Ruby (Rails) and decrypt with Python
Easy web scraping with Python and Ruby
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 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
[AtCoder explanation] Control the A, B, (C), D problems of ABC165 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC183 with Python!
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)
[AtCoder explanation] Control the A, B, C, D problems of ABC181 with Python!
3. 3. AI programming with Python