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