Solving with Ruby and Python AtCoder ABC011 C Dynamic programming

Introduction

This theme

This theme, dynamic programming

It's similar to the previously solved * AtCoder ABC 129 C in Ruby, Perl and Java (Part 2) Dynamic Programming *.

1,2 steps-> 1,2,3 subtraction

Ruby

ruby.rb


n = gets.to_i
a = Array.new(n + 1, n)
b = Array.new(n + 1, 101)
b[n] = 0
3.times do
  ng = gets.to_i
  a[ng] = -1 if ng <= n
end
n.downto(1) do |i|
  if a[i] > 0
    if i - 1 >= 0 && a[i - 1] > 0 && a[i] - 1 >= 0
      a[i - 1] = a[i] - 1
      b[i - 1] = b[i] + 1 if b[i - 1] > b[i] + 1
    end
    if i - 2 >= 0 && a[i - 2] > 0 && a[i] - 2 >= 0
      a[i - 2] = a[i] - 2
      b[i - 2] = b[i] + 1 if b[i - 2] > b[i] + 1
    end
    if i - 3 >= 0 && a[i - 3] > 0 && a[i] - 3 >= 0
      a[i - 3] = a[i] - 3
      b[i - 3] = b[i] + 1 if b[i - 3] > b[i] + 1
    end
  end
end
puts b[0] < 101 ? "YES" : "NO"

array.rb


a = Array.new(n + 1, n)
b = Array.new(n + 1, 101)

Prepare a subtraction table and a table to reduce the number of times.

ans.rb


puts b[0] < 101 ? "YES" : "NO"

Judge Yes / No by looking at the number of times when it becomes 0.

By the way, in the case of subtraction, the processing when the argument becomes negative is included, so it feels complicated. So I wrote a plus version as well.

rubyplus.rb


n = gets.to_i
a = Array.new(n + 4, n)
b = Array.new(n + 4, 101)
b[0] = 0
3.times do
  ng = gets.to_i
  a[ng] = -1 if ng <= n
end
n.times do |i|
  if a[i] > 0
    1.upto(3) do |j|
      if a[i + j] > 0
        a[i + j] = a[i] + j
        b[i + j] = b[i] + 1 if b[i + j] > b[i] + 1
      end  
    end
  end
end
puts b[n] < 101 ? "YES" : "NO"

array.rb


a = Array.new(n + 4, n)
b = Array.new(n + 4, 101)

It corresponds to a long array. Python

python.py


from sys import stdin

def main():
    input = stdin.readline
    n = int(input())
    a = [n] * (n + 4)
    b = [101] * (n + 4)
    b[0] = 0
    for i in range(3):
        ng = int(input())
        if ng <= n:
            a[ng] = -1
    for i in range(n):
        if a[i] > 0:
            for j in range(1, 4):
                if a[i + j] > 0:
                    a[i + j] = a[i] + j
                    if b[i + j] > b[i] + 1:
                        b[i + j] = b[i] + 1
    print("YES" if b[n] < 101 else "NO")
main()

Python is a plus version.

Ruby Python
Code length(Byte) 358 540
Execution time(ms) 69 29
memory(KB) 14372 9196

Summary

Recommended Posts

Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
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 and Python AtCoder ARC 059 C Least Squares
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solving with Ruby, Perl, Java and Python AtCoder diverta 2019 Programming Contest C String Manipulation
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 AtCoder ABC110 C String Manipulation
Solving with Ruby, Perl, Java and Python AtCoder ABC 107 B String Manipulation
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, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
Solved AtCoder ABC 114 C-755 with Python3
Solving with Ruby and Python AtCoder CODE FESTIVAL 2016 qual C B Priority queue
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, Perl, Java and Python AtCoder ATC 002 B
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python
Solve AtCoder ABC166 with python
ABC163 C problem with python3
ABC188 C problem with python3
Solve AtCoder ABC 186 with Python
ABC187 C problem with python
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solving in Ruby, Perl, Java, and Python AtCoder ARC 066 C Iterative Squares Hash
Solve ABC163 A ~ C with Python
[Python] Technique to reduce dimensions with DP (Dynamic Programming) [AtCoder]
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
Scraping with Node, Ruby and Python
Dynamic proxy with python, ruby, PHP
Solve ABC168 A ~ C with Python
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Solve ABC158 A ~ C with Python
AtCoder ABC168 A case expression solved in Ruby and Python
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!
[AtCoder commentary] Win the ABC165 C problem "Many Requirements" with 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
RaspberryPi L Chika with Python and C #
AtCoder ABC 174 Python
AtCoder ABC 175 Python