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 |
Recommended Posts