AtCoder Beginner Contest 113 D Number of Amidakuji

解けなかった問題の考察と解説をします。
公式解説PDFがかなりわかりやすかったので、途中詰まったところを少し詳しく。

D Number of Amidakuji

問題

beta.atcoder.jp

考察

DPで解きます。 $A(h,x)$ を $h$ 列目の左から $x$ 番目の棒にいる場合の数とします。
説明のためにあみだくじを以下のようなアスキーアートで表します。

| --- |　　| --- |

( これは4本の縦棒が作る隙間のうち、左から2つに線がある状態です。)

さて、 $(h,x)$ から $h+1$ 列目に移動したあとの位置は、 $(h,x-1)$ , $(h,x)$ $(h,x+1)$ の3つになります。
それはあみだくじの状況が次のようであるときです。
( 左から縦棒を, $x-1$ , $x$ , $x+1$ とします。)

(i) | --- |　　| ( $x-1$ に移動 )

(ii) |　　| --- | ( $x+1$ に移動 )

(iii) |　　|　　| ( $x$ に移動 )

したがって、 $(h,x)$ から $(h,x+1)$ まで移動する場合の数が $X$ だとすると、

$A(h+1,x+1) = X \times A(h,x)$

となります。同様に、 $(h,x)$ に移動する場合の数を $Y$ 、 $(h,x-1)$ に移動する場合の数を $Z$ とすると、

$A(h+1,x) = Y \times A(h,x)$

$A(h+1,x-1) = Z \times A(h,x)$

となります。

これはあくまで $x-1, x, x+1$ だけを切り出していますが、実際は縦棒の数がこれ以上多い、または少なくなります。
同じ列で、線が書ける隙間の数は $w-1$ 個になるため、 $h$ 列の線の配置パターンは $2^{w-1}$ 個です。
よって、 $(h,x)$ から $(h,x+1)$ に移動する場合の数は、 $2^{w-1}$ 個のうち (ii) を満たす場合の合計になります。
これは、(i), (iii) も同様です。

ここまでわかればあとはコードを書くだけです。

コード

コードはほぼ解説コードの写しです。
個人的に分かりづらいところがあったのでコメントをいれておきます。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

int main() {
  int h,w,k;
  cin >> h >> w >> k;
  vector<vector<int> > dp(h+1, vector<int>(w,0)); dp[0][0] = 1;

  rep(i,h) {
    rep(j,w) {
      // 同じ列の線のパターン全てをbit全探索を使って表している。
      for (int k = 0; k < 1 << (w - 1); ++k) {
        bool ok = true;
        // l番目に線があれば 1, ここでは線が隣り合っていた場合を弾いている。
        for (int l = 0; l < w-2; ++l) { 
          if (((k >> l) & 1) && ((k >> (l + 1)) & 1)) {
            ok = false;
          }
        }

        if (ok) {
          // (ii)の場合
          if (j >= 1 && ((k >> (j - 1)) & 1)) {
            dp[i+1][j-1] += dp[i][j];
            dp[i+1][j-1] %= MOD;
          } else if (j <= w - 2 && ((k >> j) & 1)) {
          // (i) の場合
            dp[i+1][j+1] += dp[i][j];
            dp[i+1][j+1] %= MOD;
          } else {
          // (iii) の場合
            dp[i+1][j] += dp[i][j];
            dp[i+1][j] %= MOD;
          }
        }
      }
    }
  }

  cout << dp[h][k-1] << endl;
}