Why not login to Qiita and try out its useful features?

We'll deliver articles that match you.

You can read useful information later.

1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Posted at

はじめに

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 に詳しくなった
1
0
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?