こんにちは！じゃいごテックのあつしです。
今回は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, qとq個の整数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, qとq個の整数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を出力してみると値を更新する過程が見られます。
ノートに書いてみるのも良いかもしれません。
