Number of Amidakuji [AtCoder Beginner Contest 113 D]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_d

前提知識

• https://www.hamayanhamayan.com/entry/2017/02/27/021246:titie=動的計画法

解説

https://beta.atcoder.jp/contests/abc113/submissions/3558659

dpで解く。
1,2,3,...,W本目ではなく、0,1,2,...,W-1本目と考えて解く。
dp[h][k] := 高さhまであみだくじを構築していて、0本目の縦棒がk本目に遷移する組み合わせ
0本目がどこに遷移したかだけが関係あるので、他の縦棒の遷移先については抽象化できる。
dpの遷移が難しいポイントであるが、高さhの地点で作れるあみだくじについて全列挙していこう。

まず、W本あるなら、間はW-1本ある。
この間について線を引く、線を引かないの2通りがあり、2^(W-1)通りがある。
これを全列挙するのに、rep(msk, 0, 1 << (W - 1))のようにして書く。
これで0,1の全列挙ができた。
これで大体の条件は満たせているが、「どの2つの横棒も端点を共有しない」という条件を満たせてないため、
check関数で満たしているかチェックしよう。
　
これでvalidな線引ができたため、0本目がk本目に遷移している場合なら、

• k番目に線がある→k本目からk+1本目へ
• k-1番目に線がある→k本目からk-1本目へ
• どちらも無い→k本目からk本目へ

遷移するので、これで遷移式を書く。

int H, W, K;
mint dp[101][8];
//---------------------------------------------------------------------------------------------------
int check(int msk) {
    rep(i, 0, W - 2) {
        int a = (msk >> i) & 1;
        int b = (msk >> (i + 1)) & 1;
        if (a and b) return 0;
    }
    return 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> K;
    K--;
 
    dp[0][0] = 1;
    rep(h, 0, H) rep(k, 0, W) rep(msk, 0, 1 << (W - 1)) if (check(msk)) {
        if (msk & (1 << k)) dp[h + 1][k + 1] += dp[h][k];
        else if (0 < k and msk & (1 << (k - 1))) dp[h + 1][k - 1] += dp[h][k];
        else dp[h + 1][k] += dp[h][k];
    }
 
    cout << dp[H][K] << endl;
}