[AtCoder] ABC 113 D – Number of Amidakuji

2019年5月15日

問題

方針

ある高さの正しい横棒の配置

ある高さの横棒の配置のパターンを考えます。横棒は縦棒の間に置くことができるので、縦棒の本数 \( W \) が \( W = 1 \) のときは横棒を置くことができません。そうではないとき、縦棒の間に横棒を置くか置かないかの \( 2 \) 通りがあるので、全体で \( 2^{W – 1} \) 通りあります。このパターンは \( W – 1 \) ビットのビット列として表すことができます。

次にこのパターンから正しくない横棒の置き方をしているものを取り除きます。これは得られたビット列において、\( 1 \) が隣り合うときとなります。例えば、\( W = 4 \) のとき、以下のパターンが得られます。

あみだくじ

これをビット列で表現すると、左から、

\( 000 \), \( 100 \), \( 001\), \( 010 \)

となります。

動的計画法

横棒の置き方は高さに依存せずにおくことができるので、高さ \( 1 \) から \( H \) まで順々に数え上げていくことができます。ここで、配列 \( dp[i][j] \) 高さ \( 0 \) における縦棒 \( 1 \) から高さ \( i \) における縦棒 \( j \) までの行き方とします。初期値は、\( dp[0][0] = 1\) とします。また、以降では縦棒の添え字を \( 0 \) オリジンとして考えます。この配列の更新の仕方は、上記の画像を例にすると次のように記述でます。

\[
\begin {align}
dp[i][0] &= 3dp[i – 1][0] + dp[i – 1][1] \\
dp[i][1] &= dp[i – 1][0] + 2dp[i-1][1] + dp[i – 1][2]\\
dp[i][2] &= dp[i – 1][1] + 2dp[i-1][2] + dp[i-1][3]\\
dp[i][3] &= dp[i – 1][2] + 3dp[i-1][3] \\
\end {align}
\]

したがって、正しい横棒の配置パターンを表すビット列を予め計算しておくことで、動的計画法の更新を行うことができます。

コード

提出したコード

ビット列の生成

動的計画法