水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Beginner Contest 113:D - Number of Amidakuji

問題

beta.atcoder.jp

解法

ぱっと見 DP をしたい気持ちになるので,以下のように DP を定義する:

dp(h, w) := スタートから h 行 w 列に行くまでのあみだくじの通り数の合計

後は,DP の遷移を考える.この時,今いる行の次(すなわち h + 1 行目)のどこに行くかで場合分けする.これは,左に移るか,右に移るか,このまま下に行くかの3通りある.3通りそれぞれの場合になる h 行目の横線の入れ方を bit 全探索する.横線が隣り合ってはいけないという制約に注意して実装すると,求める dp(h, w) は以下のように求められる:

dp(h, w) = dp(h + 1, w - 1) * (左に移れる横線の入れ方の通り数) + dp(h + 1, w) * (このまま下に行ける横線の入れ方の通り数) + dp(h + 1, w + 1) * (右に移れる横線の入れ方の通り数)

O(HW * (2^W)).

解答

beta.atcoder.jp

コンテスト中に解けなかった.シンプルではあるが,DP 上で bit 全探索をするのは斬新だった.

f:id:babcs2035:20181105204918p:plain