Ruby と Python で解く AtCoder ABC011 C 動的計画法

19517 ワード
Ruby AtCoder Python 新人プログラマ応援 Ruby テキストリンク

はじめに

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 に詳しくなった
Python-週の辞書1-7
【Python 3】基本データ型-リスト(list)