[Ruby]paiza DPメニュー 3項間漸化式 2: STEP5, FINAL

こんにちは！じゃいごテックのあつしです。

今回はpaiza DPメニュー 「セクション1【漸化式】 3項間漸化式 2- STEP5, FINAL」 を解説します。

この問題集は動的計画法(Dynamic Programming, DP)に関する6個のセクションで構成されています。
各セクションにはそれぞれ複数のSTEP問題とFINAL問題があり、STEP問題を解いていけばFINAL問題も解けるはず！となっています。

STEP問題 5 を解いてみる

簡単な解説は付けていますが、難しいと感じたら下記の記事も参考にしてみて下さい。

STEP5: 3項間漸化式 1 (paizaランク B 相当)

STEP5 はフィボナッチ数列の第k項を出力する問題です。フィボナッチ数列は下記の漸化式で表される数列です。

漸化式

• a_1 = 1（第1項）
• a_2 = 1（第2項）
• a_n = a_{n-2} + a_{n-1} (n ≧ 3)

解答例

INPUT1 = <<~"EOS"
  7
EOS
OUTPUT1 = <<~"EOS"
  13
EOS

def solve(input_data)
  k = input_data.to_i

  # dpテーブル初期化
  # n = 1 : 1
  # n = 2 : 1
  dp = [1, 1]

  # dpテーブル更新
  # n >= 3 : dp[n - 2] + dp[n - 1]
  (k - 2).times do |n|
    dp << dp[-2] + dp[-1]
  end

  # k 項の値を返す
  dp[k - 1]
end

puts solve(STDIN.read)

# 確認用コード
# puts solve(INPUT1)
# > 13

• 整数kを受け取る。
• dpに[1, 1]を代入する。（dp[0]に第1項=1、 dp[1]に第2項=1が入る）
• k-2回の繰り返し処理を設定する。
  (第2項までは求められているので、第3項を求めるには3-2=1回処理を行う)
  • dp末尾にdp[-2]+dp[-1]を追加する。
• dp[k-1]に第k項の値が入っているので返す。
  (dp[0]: 1項の値, dp[1]: 2項の値, dp[2]: 3項の値, ..., dp[k-1]: k項の値)

FINAL問題: 3項間漸化式 2 (paizaランク B 相当)

※ paizaレベルアップ問題集 DPメニューより

問題

a_{k_1}
a_{k_2}
...
a_{k_Q}

攻略ポイント

問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = <<~"EOS"
  5
  1
  2
  3
  4
  3
EOS
OUTPUT1 = <<~"EOS"
  1
  1
  2
  3
  2
EOS

# 確認用コード
p INPUT1
# > "5\n1\n2\n3\n4\n3\n"
p OUTPUT1
# > "1\n1\n2\n3\n2\n"

続いて、問題を解くsolveメソッドを変数の下に定義し、入力データを受け取る処理を書きます。

def solve(input_lines)
  q, *ary_k = input_lines.split("\n").map(&:to_i)

  # 確認用コード
  ary_k
end

# 確認用コード
p solve(INPUT1)
# > [1, 2, 3, 4, 3]

データが正しく受け取れていれば、solve メソッドに処理を追加していきます。

• 整数qと続くq行の整数を配列ary_kに格納する。（整数qは今回は使ってない）
• 配列ary_kの最大値を探してk_maxに代入する。
• dpに[1, 1]を代入する。（dp[0]に第1項=1、 dp[1]に第2項=1が入る）
• k_max-2回の繰り返し処理を設定する。
  (第2項までは求められているので、第k_max項を求めるにはk_max-2回処理を行う)
  • dp末尾にdp[-2]+dp[-1]を追加する。
• ary_kの先頭から順に要素kを取り出してdp[k-1]を参照した値を配列で返す。
  (dp[0]: 1項の値, dp[1]: 2項の値, dp[2]: 3項の値, ..., dp[k-1]: k項の値)

def solve(input_lines)
  q, *ary_k = input_lines.split("\n").map(&:to_i)

  # dpテーブル初期化
  # n = 1 : 1
  # n = 2 : 1
  dp = [1, 1]

  # 最大の項
  k_max = ary_k.max

  # dpテーブル更新
  # n >= 3 : dp[n - 2] + dp[n - 1]
  (k_max - 2).times do |n|
    dp << dp[-2] + dp[-1]
  end

  # ary_k の先頭から順に k 項の値を返した結果を配列で返す
  ary_k.map { |k| dp[k - 1] }
end

# 確認用コード
p solve(INPUT1)
# > [1, 1, 2, 3, 2]
p solve(INPUT1) == OUTPUT1
# > false

あとは出力形式を整えれば完成です。

p solve(INPUT1) == OUTPUT1 -> true を確認するために、出力の配列を改行で結合して末尾に改行を加えます。

def solve(input_lines)
  q, *ary_k = input_lines.split("\n").map(&:to_i)

  # dpテーブル初期化
  # n = 1 : 1
  # n = 2 : 1
  dp = [1, 1]

  # 最大の項
  k_max = ary_k.max

  # dpテーブル更新
  # n >= 3 : dp[n - 2] + dp[n - 1]
  (k_max - 2).times do |n|
    dp << dp[-2] + dp[-1]
  end

  # ary_k の先頭から順に k 項の値を返した結果を改行区切りの配列にして末尾に改行を追加
  ary_k.map { |k| dp[k - 1] }.join("\n") << "\n"
end

# 確認用コード
p solve(INPUT1)
# > "1\n1\n2\n3\n2\n"
p solve(INPUT1) == OUTPUT1
# > true

入出力例での動作確認が出来ましたので、標準入力からのデータ受け取りに変更して、手動で動作確認をしたら提出します。
複数行のデータ受け取りなので STDIN.read を使います。（入力終了は Ctrl+D 又は Ctrl+Z)

解答コード

def solve(input_lines)
  q, *ary_k = input_lines.split("\n").map(&:to_i)

  # dpテーブル初期化
  # n = 1 : 1
  # n = 2 : 1
  dp = [1, 1]

  # 最大の項
  k_max = ary_k.max

  # dpテーブル更新
  # n >= 3 : dp[n - 2] + dp[n - 1]
  (k_max - 2).times do |n|
    dp << dp[-2] + dp[-1]
  end

  # ary_k の先頭から順に k 項の値を返した結果を改行区切りの配列にして末尾に改行を追加
  ary_k.map { |k| dp[k - 1] }.join("\n") << "\n"
end

puts solve(STDIN.read)

（参考）トップダウン方式のDP

def fib(n)
  return [1] * n if n < 3

  dp = fib(n - 1)
  dp << dp[-1] + dp[-2]
end

def solve(input_data)
  q, *ary_k = input_data.split("\n").map(&:to_i)

  # 最大の項
  k_max = ary_k.max

  # 0 ~ k_max 項までの dpテーブル
  dp = fib(k_max)

  # ary_k の先頭から順に項の値を返す
  ary_k.map { |k| dp[k - 1] }
end

puts solve(STDIN.read)

# 確認用コード
# puts solve(INPUT1)
# > 1
# > 1
# > 2
# > 3
# > 2

今回のまとめ

セクション1では基本的な漸化式の処理を扱いました。

暗算出来るような簡単な問題でもDPに置き換えて考えてみると少し難しく感じたのではないでしょうか？
繰り返し中のdpを出力してみたり、ノートに書いてみるのも良いかもしれませんね。