先日 AtCoder のコンテストに 2 年ぶりに出場したら、とても熱中しました。現在のランクは灰色で初心者同然なのですが、ランクアップのためにはいくつかのアルゴリズムの習得が必須となることを知りました。
必要なアルゴリズムの中でも動的計画法は汎用性が高く、いろいろな問題に適用できるため優先して学習する必要がありそうです。
私は競技プログラミングにおいては、業務と同様 Ruby を利用しています。
競技プログラミング関連の情報のサンプルコードはだいたい C++ で実装されていて、Ruby による情報は少なめです。
本記事では、動的計画法の典型問題を Ruby で解きサンプルコードを掲載することで、Ruby で競技プログラミングをする方の参考になれば幸いです。
題材は、Educational DP Contest / DP まとめコンテスト - AtCoderの 問題とします。
解いた問題から、順次足していく予定です。
動的計画法を利用時のポイント
動的計画法の問題を何問かといてみて、解き方に規則性があることに気づいたのでその共通の規則性についてまとめます。
- 数学的要素が強いので、ノートとペンを使って頭を整理する
- 問題文から、動的計画法テーブル(サンプルコードでは
dpと定義)に格納する型(数値 or 真偽値)と値を決める - 動的計画法テーブルの添字(インデックス)を決める
- 動的計画法テーブルをの初期値を決める(数値ならば0やFloat::INFINITY、真偽値ならば true/false を使うケースが多い)
- 動的計画法テーブルの
i+1項の求め方を漸化式としに落とし込む(DP[i+1] = DP[i] + Xの形式) -
i+1項目を求める際の、重さや個数の制約条件を抽出する - 添字をベースにして、ループの回数を決める
A - Frog 1
問題 https://atcoder.jp/contests/dp/tasks/dp_a
# 添字の制約
# 0 <= i <= N
# dpの定義
# i番目の足場までにかかるコストの最小値
# 漸化式
# dp[i + 1] = [dp[i + 1], dp[i] + (h[i + 1] - h[i]).abs].min if i + 2 <= N
# dp[i + 2] = [dp[i + 2], dp[i] + (h[i + 2] - h[i]).abs].min if i + 3 <= N
# 初期化
# dp[0] = 0
# 出力
# dp[N - 1]
N, K = gets.chomp.split.map(&:to_i)
h = gets.chomp.split.map(&:to_i)
dp = Array.new(N + 1, Float::INFINITY)
dp[0] = 0
N.times do |i|
dp[i + 1] = [dp[i + 1], dp[i] + (h[i + 1] - h[i]).abs].min if i + 2 <= N
dp[i + 2] = [dp[i + 2], dp[i] + (h[i + 2] - h[i]).abs].min if i + 3 <= N
end
puts dp[N - 1]
B - Frog 2
問題 https://atcoder.jp/contests/dp/tasks/dp_b
# 添字の制約
# 0 <= i <= N
# 1 <= j <= K
# i + j < K
# dpの定義
# i番目の足場までにかかるコストの最小値
# 漸化式
# dp[i + j] = [dp[i + j], dp[i] + (h[i + j] - h[i]).abs].min
# 初期化
# dp[0] = 0
# 出力
# dp[N - 1]
N, K = gets.chomp.split.map(&:to_i)
h = gets.chomp.split.map(&:to_i)
dp = Array.new(N + 1, Float::INFINITY)
dp[0] = 0
N.times do |i|
(1..K).each do |j|
next if i + j >= N
dp[i + j] = [dp[i + j], dp[i] + (h[i + j] - h[i]).abs].min
end
end
puts dp[N - 1]
C - Vacation
問題 https://atcoder.jp/contests/dp/tasks/dp_c
# dpの定義
# dp[i][j] i日目に活動jを選んだときの幸福度の最大値
# 添字の制約
# 0 <= i <= N - 1
# 0 <= j <= 2
# k = [0, 1, 2] - [j]
# i+1項目の漸化式
# dp[i + 1][j] = [dp[i + 1][j], dp[i][j] + happiness].max
# 初期化
# dp[0][0]=0
# 出力
# dp[N]の最大値
N = gets.chomp.to_i
days = Array.new(N) { gets.split.map(&:to_i) }
dp = Array.new(N + 1) { Array.new(3, 0) }
days.each_with_index do |day, i|
day.each_with_index do |happiness, j|
prev = [0, 1, 2] - [j]
prev.each do |k|
dp[i + 1][j] = [dp[i + 1][j].to_i, dp[i][k].to_i + happiness].max
end
end
end
puts dp[N].max
D - Knapsack 1
問題 https://atcoder.jp/contests/dp/tasks/dp_d
# 添字の制約
# 0 <= i <= N - 1
# 1 <= j <= W
# 0 <= w <= j
# dpの定義
# dp[i][j] i個目までの品物を選び、重さjであるときの価値の最大値
# i+1項目の漸化式
# dp[i + 1][j] = dp[i][j - weight] + value (j >= weight)
# dp[i + 1][j] = dp[i][j] (j < weigh)
# 出力
# dp[N][W]
N, W = gets.split.map(&:to_i)
wv = Array.new(N) { gets.split.map(&:to_i) }
dp = Array.new(N + 1) { Array.new(W + 1, 0) }
N.times do |i|
(0..W).each do |j|
weight, value = wv[i]
if j >= weight
dp[i + 1][j] = [dp[i][j], dp[i][j - weight] + value].max
else
dp[i + 1][j] = dp[i][j]
end
end
end
puts dp[N][W]
E - Knapsack 2
問題 https://atcoder.jp/contests/dp/tasks/dp_e
# 添字の制約
# 0 <= i <= n - 1
# 1 <= j <= value_max
# j - value >= 0
# dpの定義
# dp[i][j] i個目までの品物を選び、価値がjであるときの価値の最大値
# i+1項目の漸化式
# dp[i + 1][j] = dp[i][j - weight] + value (j >= weight)
# dp[i + 1][j] = dp[i][j] (j < weigh)
# 初期化
# dp[0][0]=0
# 出力
# dp[n][w]の最大値
n, w = gets.split.map(&:to_i)
value_max = 10**5 + 1
wv = Array.new(n) { gets.split.map(&:to_i) }
dp = Array.new(n + 1) { Array.new(value_max + 1, Float::INFINITY) }
dp[0][0] = 0
n.times do |i|
weight, value = wv[i]
value_max.times do |j|
if j - value >= 0
dp[i + 1][j] = [dp[i][j], dp[i][j - value] + weight].min
else
dp[i + 1][j] = dp[i][j]
end
end
end
max = 0
dp[n].each_with_index do |num, index|
max = index if num <= w
end
puts max
参考
解法や高速化テクニックなど大いに参考にさせていただきました。