はじめに
AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
今回のお題
AtCoder Beginner Contest C - 123引き算
Difficulty: 761
今回のテーマ、動的計画法
以前解きました、*Ruby と Perl と Java で解く AtCoder ABC 129 C (後編) 動的計画法*と似た感じです。
1,2段飛び->1,2,3の引き算
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)
引き算のテーブルと、回数を控えるテーブルを用意します。
ans.rb
puts b[0] < 101 ? "YES" : "NO"
0
になった時の回数をみて、Yes/Noを判定します。
ところで引き算の場合、引数がマイナスになった時の処理が入りますので、煩雑な感じがします。
そこで、プラス版も書いてみました。
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)
配列を長めにとって対応しています。
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
はプラス版です。
Ruby | Python | |
---|---|---|
コード長 (Byte) | 358 | 540 |
実行時間 (ms) | 69 | 29 |
メモリ (KB) | 14372 | 9196 |
まとめ
- ABC 011 C を解いた
- Ruby に詳しくなった
- Python に詳しくなった