ABC113 D - Number of Amidakuji (400点)
優秀なフレンズの助言をもらいながらACできたので、忘れないうちに記事にします。
#問題
概要(適当なのでちゃんと公式の問題文を読んでね)
縦棒の長さと本数が与えられる。縦棒の間に好きに横線を引いて、あみだくじを作る。番目の棒の上端から, 横線があれば必ずそれを通るというルールで下へたどったときに、最終的にたどり着く縦棒の番号がとなるような「正しいあみだくじ」の本数をで割った余りを求めなさい。
制約
・
・
・
#考察
考えの流れ
- ある高さにおける横線の引き方は高々通り
- ある高さの本目に至るのが何通りかわかっていたらについても計算できるんじゃないか
- 各高さについて分割して考えられそう
- ある高さの本目に至る状態をまとめて扱えそう
- DPかな
- 計算量を見積もる。ある高さにおいて、全ての横線の引き方である通りの状態を考え、それぞれがあみだくじの要件を満たしているかを計本について調べる。これを全ての高さ()について行うので、で間に合いそう
上記のような考察でDPっぽいことがわかったので、状態と遷移を考えます。 を、高さの番目(0-indexed)に至るのに何通りあるか、と定めます。
遷移を考えます。 今、高さ、番目の横線にいるとします。ここに至るまでに通り存在します。
に向かう横線があれば、番目の横線に移動して次の高さに進みます。
に向かう横線があれば、番目の横線に移動して次の高さに進みます。
両隣に横線がなかったら、同じ番目のまま次の高さに進みます。
ちなみに、両隣に横線があることはありません。正しくないあみだくじだからです。そのような正しくないあみだくじは予め弾いておきます。
初期条件はです。高さ、すなわち、まだどの高さにも移動してないとき、番目の横棒にいるのは通りだからです。
H, W, K = gets.split.map(&:to_i)
MOD = 10 ** 9 + 7
dp = Array.new(H + 1) { Array.new(W, 0) }
dp[0][0] = 1
H.times do |h|
# ある高さにおいて、2^(W-1)通りの横線の引き方がある
(0...(1 << (W - 1))).each do |bit|
# check
# 正しくないあみだくじを弾く
# 1が連続して2つあったらアウト
flag = false
(1...W).each do |i|
if bit[i] == 1 && bit[i - 1] == 1
flag = true
end
end
next if flag
# transition
# 横線をそれぞれ調べて遷移
W.times do |w|
if w != W - 1 && bit[w] == 1
target = w + 1
elsif w != 0 && bit[w - 1] == 1
target = w - 1
else
target = w
end
dp[h + 1][target] = (dp[h + 1][target] + dp[h][w]) % MOD
end
end
end
puts dp[H][K - 1]
#学び
DPを使うところまで漕ぎ着ければ、DPに慣れてる人なら解けそう。 DPに至る思考として
- 分割して解けないか
- まとめて扱えないか
みたいなのがありそう。
DPの状態と遷移自体はシンプルなので教育的なDP問題だと思う。