[AtCoder] ABC113 D – Number of Amidakuji

Number of Amidakuji

ビット全探索と動的計画法を組み合わせて解きます。コンテスト中には何をすればよいのか分かりませんでした。

考え方

横棒の置き方

ある高さの横棒の置き方のパターンは、縦棒の間に棒を置くか置かないかの2通りで、置くスペースは \( W – 1 \) 個あるので、全てで \( 2^{W – 1} \) 通りあります。

このパターンは長さ \( W – 1\) のビット配列で表すことができます。ここで、条件を満たすビット配列は、1が隣り合っていないものになります。

したがって、全てのビット配列の中から1が隣り合っているものを除外します。

この横棒の置き方は高さに依存せずに置くことができるので、リストに格納して動的計画法の計算のときに使いまわします。

動的計画法

あみだくじの状態は、現在位置している高さと横棒の位置で表すことができます。イメージ的には平面座標の格子点でしょうか。

高さ \( i \) におけるあみだくじの状況は \( i – 1 \) の高さから求めることができます。ここで、次の配列を考えます。

\( dp[i][j]: \) 高さ \( i \) における横棒 \( j \) に行くパターン。

初期状態は、高さ0の横棒1から始めるので、\( dp[0][1] = 1\) とします。次に高さ1のあみだくじの状態を求めるには、全ての棒の置き方と高さ0のあみだくじの状態を考慮して求めます。

具体例を挙げた方が考え易いので、\( W = 4 \) として考えます。このとき、棒の置き方は、5通りありますが、その中で4通りを取り上げます。(4通りのつもりで記事を書いていました。)

上記の画像を参考にして、

\( dp[i – 1][1] = a_1\)、\( dp[i – 1][2] = a_1\)、\( dp[i – 1][3] = a_1\)、\( dp[i – 1][4] = a_1\) とします。このとき、高さ \( i \) におけるその地点への行き方は、

\[
\begin{eqnarray}
dp[i][1] &=& a_1 + a_2 + a_1 + a_2 \\
dp[i][2] &=& a_2 + a_1 + a_3 + a_1 \\
dp[i][3] &=& a_3 + a_3 + a_2 + a_4 \\
dp[i][4] &=& a_4 + a_4 + a_4 + a_3
\end{eqnarray}
\]

となります。このような計算を行えば解答を得ることができます。

横棒があるときはその縦棒に対応する要素を交換するというプログラムを書けばこの操作を行うことができると思います。つまり、 \( dp[i – 1][\cdot]\) の配列をコピーしておいて、ビット配列ごとに要素の交換を行い足し合わせていけばよいです。

ソースコード

感想

他の人の解説を読んでも理解できない部分があったので、自分で考えて見ると、あみだくじの横棒が要素の交換を意味することに気が付き正解することができました。あみだくじは互換の積を学んだ時に出てきたと思いますが、役立たせることはできませんでした。

今度はD問題を考えられるように頑張ります。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする