paiza プログラミング

[Ruby]paiza DPメニュー 3項間漸化式 2: STEP1~4

dpメニューSTEP1-4

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

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

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

STEP問題 1~4 を解いてみる

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

STEP1: 2項間漸化式 1 (paizaランク C 相当)

STEP1 は整数x, d, kと下記の漸化式が与えられたときk項の値を出力する問題です。

漸化式

  • a_1 = x
  • a_n = a_{n-1} + d (n ≧ 2)

初期値(k=1)の値がxで、kが1増えるごとにその前の値にdを足すと言う計算です。

解答例

INPUT1 = <<~"EOS"
  0 7 9
EOS
OUTPUT1 = <<~"EOS"
  56
EOS

def solve(input_lines)
  x, d, k = input_lines.split.map(&:to_i)

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

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

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

p solve(STDIN.read)

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

入出力例で x = 0, d = 7, k = 9 が与えられたとき、y = 7x - 7 ->7 * 9 - 7 = 56
と、暗算してしまったかもしれませんが、素直にDPで解いてみましょう。

  • 整数x, d, kを受け取る。
  • dp[0]xを代入する。(dp[0]に第1項の答えが入る)
  • k-1回の繰り返し処理を設定する。
    • dp末尾dを足した値を、dp末尾に追加する。
  • dp[k-1]k項の値が入っているので返す。
    (dp[0]: 1項の値, dp[1]: 2項の値, dp[2]: 3項の値, ..., dp[k-1]: k項の値)

STEP2: 2項間漸化式 2 (paizaランク C 相当)

STEP2 は整数x, d, qq個整数k_1,k_2, ..., k_q、下記の漸化式が与えられたとき、各k項の値を改行区切りで出力する問題です。

漸化式

  • a_1 = x
  • a_n = a_{n-1} + d (n ≧ 2)

解答例

INPUT1 = <<~"EOS"
  0 7
  5
  1
  2
  3
  4
  5
EOS
OUTPUT1 = <<~"EOS"
  0
  7
  14
  21
  28
EOS

def solve(input_lines)
  x, d, q, *ary_k = input_lines.split.map(&:to_i)

  # 最大の項
  k_max = ary_k.max
  # dpテーブル初期化
  # n = 1 : x
  dp = [x]

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

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

puts solve(STDIN.read)

# 確認用コード
# puts solve(INPUT1)
# > 0
# > 7
# > 14
# > 21
# > 28

最大の項k_maxを見つけて、k_max項までのdpテーブルを作成してary_kの先頭から順に値を出力します。

    • 整数x, d, k, qを受け取り、続くq行の整数をary_kに格納する。
    • ary_kの中から最大値を探してk_maxとする。
    • dp[0]xを代入する。(dp[0]に第1項の答えが入る)
    • k_max-1回の繰り返し処理を設定する。
      • dp末尾dを足した値を、dp末尾に追加する。
    • ary_kの先頭から順に要素kを取り出してdp[k-1]を参照した値を配列で返す。
      (dp[0]: 1項の値, dp[1]: 2項の値, dp[2]: 3項の値, ..., dp[k-1]: k項の値)

STEP3: 特殊な2項間漸化式 1 (paizaランク B 相当)

STEP3 は整数x, d_1, d_2, kと下記の漸化式が与えられたとき、k項の値を力する問題です。

漸化式

  • a_1 = x
  • a_n = a_{n-1} + d_1 (n が奇数のとき、n ≧ 3)
  • a_n = a_{n-1} + d_2 (n が偶数のとき)

解答例

INPUT1 = <<~"EOS"
  5 -7 10 5
EOS
OUTPUT1 = <<~"EOS"
  11
EOS

def solve(input_lines)
  x, d1, d2, k = input_lines.split.map(&:to_i)

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

  # dpテーブル更新
  # n >= 2
  (k - 1).times do
    dp << if dp.size.even?
      # dpの項数が偶数のとき求める項は奇数
      dp[-1] + d1
    else
      # dpの項数が奇数のとき求める項は偶数
      dp[-1] + d2
    end
  end

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

puts solve(STDIN.read)

# 確認用コード
# p solve(INPUT1)
# > 11
  • 整数x, d_1, d_2, kを受け取る。
  • dp[0]xを代入する。(dp[0]に第1項の答えが入る)
  • k-1回の繰り返し処理を設定する。
    • 求める項が奇数ならdp末尾d_1を足した値を、dp末尾に追加する。
    • 求める項が偶数ならdp末尾d_2を足した値を、dp末尾に追加する。
  • dp[k-1]k項の値が入っているので返す。
    (dp[0]: 1項の値, dp[1]: 2項の値, dp[2]: 3項の値, ..., dp[k-1]: k項の値)

STEP4: 特殊な2項間漸化式 2 (paizaランク B 相当)

STEP4 は整数x, d_1, d_2, qq個整数k_1,k_2, ..., k_q、下記の漸化式が与えられたとき、各k項の値を改行区切りで出力する問題です。

漸化式

  • a_1 = x
  • a_n = a_{n-1} + d_1 (n が奇数のとき、n ≧ 3)
  • a_n = a_{n-1} + d_2 (n が偶数のとき)

解答例

INPUT1 = <<~"EOS"
  3 7 -4
  5
  1
  2
  3
  4
  10
EOS
OUTPUT1 = <<~"EOS"
  3
  -1
  6
  2
  11
EOS

def solve(input_lines)
  x, d1, d2, q, *ary_k = input_lines.split.map(&:to_i)

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

  # 最大の項
  k_max = ary_k.max

  # dpテーブル更新
  # n >= 2
  (ary_k.max - 1).times do
    dp << if dp.size.even?
      # 項が偶数のとき
      dp[-1] + d1
    else
      # 項が奇数のとき
      dp[-1] + d2
    end
  end

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

puts solve(STDIN.read)

# 確認用コード
# puts solve(INPUT1)
# > 3
# > -1
# > 6
# > 2
# > 11
  • 整数x, d_1, d_2, qを受け取り、続くq行の整数をary_kに格納する。
  • ary_kの中から最大値を探してk_maxとする。
  • dp[0]xを代入する。(dp[0]に第1項の答えが入る)
  • k_max-1回の繰り返し処理を設定する。
    • 求める項が奇数ならdp末尾d_1を足した値を、dp末尾に追加する。
    • 求める項が偶数ならdp末尾d_2を足した値を、dp末尾に追加する。
  • ary_kの先頭から順に要素kを取り出してdp[k-1]を参照した値を配列で返す。
    (dp[0]: 1項の値, dp[1]: 2項の値, dp[2]: 3項の値, ..., dp[k-1]: k項の値)

今回のまとめ

STEP1からSTEP4は基本的な漸化式を取り扱いました。

繰り返し中のdpを出力してみると値を更新する過程が見られます。
ノートに書いてみるのも良いかもしれません。



【PR】アルゴリズム学習でお世話になった本


アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。






通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。







通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。







通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者~中級者向けに書かれているので解説が非常に丁寧です。







Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。


-paiza, プログラミング
-, , ,

© 2024 じゃいごテック