ABC113-D：Number of Amidakuji(400)

問題

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

制約

  • 1 \le H \le 100
  • 1 \le W \le 8
  • 1 \le K \le W

考え方

あみだくじについて上 (H=1) から順番に組み合わせを決めていく。以下のようなDPを考える。

dp[i][j] := 高さ i で横から j 番目にいるときのあみだくじの組み合わせの数

とする。あみだくじの横棒の線の引き方の組み合わせは 2^W-1 個存在する。それぞれについて右・左・まっすぐに遷移できるか確認する。

まず、横棒が 2 つ連続でつながっている場合は条件を満たさないので遷移できない。そうでない場合は遷移できるのであみだくじの枠からはみ出さないように遷移すれば良い。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int H = in.nextInt(), W = in.nextInt(), K = in.nextInt();
            long[][] dp = new long[H+1][W+1];
            dp[0][0] = 1;

            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    for (int bit = 0; bit < 1 << (W-1); bit++) {
                        boolean ok = true;
                        for (int l = 0; l < W-2; l++) {
                            // 横棒がつながる場合は除く
                            if ((bit >> l & 1) == 1 && (bit >> (l+1) & 1) == 1) {
                                ok = false;
                            }
                        }

                        if (ok) {
                            // 左に遷移
                            if (j >= 1 && (bit >> j-1 & 1) == 1) {
                                dp[i+1][j-1] += dp[i][j];
                                dp[i+1][j-1] %= MOD;

                                // 右に遷移
                            } else if (j <= W-2 && (bit >> j & 1) == 1) {
                                dp[i+1][j+1] += dp[i][j];
                                dp[i+1][j+1] %= MOD;

                                // まっすぐ遷移
                            } else {
                                dp[i+1][j] += dp[i][j];
                                dp[i+1][j] %= MOD;
                            }
                        }
                    }
                }
            }

            out.println(dp[H][K-1]);

        }

ポイント

  • 遷移できる条件を考える

類題

雑記

点と横棒の関係がうまく実装できなくて、本番では解けませんでした。