D - Number of Amidakuji
はじめに
競技プログラミング、AtCoder Beginner Contest 113
D - Number of Amidakuji
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
あみだくじは, 日本に古くから伝わる伝統的なくじ引きである. あみだくじを作るには, まず W本の平行な縦線を引き, 次にそれらを繋ぐ横線を引いていく. それぞれの縦棒の長さはH+1[cm]であり、 横線の端点となれるのは上から1,2,3,...,H[cm]の位置のみである. ここで,「正しいあみだくじ」とは,以下のような条件を満たすあみだくじのことである. ・どの2つの横棒も端点を共有しない. ・それぞれの横棒の 2つの端点は同じ高さになければならない. ・横棒は隣り合う縦線を繋がなければならない. 縦棒1の上端から, 横線があれば必ずそれを通るというルールで下へたどったときに, 最終的にたどり着く縦棒の番号がKとなるような 「正しいあみだくじ」の本数を1,000,000,007で割った余りを求めなさい.
制約
・Hは1以上100以下の整数 ・Wは1以上8以下の整数 ・Kは1以上W以下の整数
入力
入力は以下の形式で標準入力から与えられる。 H W K
出力
条件を満たすあみだくじの本数を1,000,000,007で割った余りを出力しなさい.
解き方
この問題を解くには2ステップ踏むことが必要である。
まず、
あみだくじの一つの行において、
あみだくじの横棒の組み合わせをbit全探索で出し
そのあとに動的計画法を用いて
それぞれの地点におけるパターンの数を全探索する
以下、bit探索と動的計画法を完全に分けて解く方法です
全体の流れ
入力3(2,3,3)を用いると以下のようなイメージになる
①bit全探索であみだくじの横棒の組み合わせを洗い出す
入力から縦棒は3本なので、横棒が入る箇所は2つ
横棒があるを○、横棒がないを×とすると組み合わせは以下の3通りになる
○× ×○ ××
②動的計画法を用いて、それぞれの地点におけるパターンの数を出す
入力よりH=2、K=3なので
答えは右下の点となり1通り(詳細は下で解説)
ここから詳しく解説していく
解いていく順序としては逆だが
bit全探索時に
何の情報を保存すればよいのかが分かり易くなるため、
動的計画法から解説していく。
1.動的計画法
まず、動的計画法とは
通過点の値を保存し、
利用しながら先に進んでいく方法です
文章で説明すると難しいので、以下問題を解きながら解説していきます
今回のあみだくじの例でいえば、
ゴールがKの示す部分(黄緑色の丸がついている部分)、
通過点はあみだくじの各地点(赤い点がついている部分)です
以下、H=2、K=3の図
この各赤い地点の値を出しつつ、
上から下へ向かい
Kというゴールを目指します。
それでは、以下手順です。
入力は「2 3 3」を想定しています。
bit探索で出す以下のパターンを使用します。
横棒があるを○、横棒がないを×とします
○× ×○ ××
①スタート地点
問題文から、スタート地点は、一番左上の赤い点です
この点に来るのは「一番初め」以外にはあり得ないので
この地点に来れるのは「1通り」だけです
②0番上の行
スタート地点である
一番左以外の赤い点は到達することはできないので
全て0通りとなります
③1番目の行
*一番左の赤い点
一番左の点に到達するには、
以下の2パターン方法が考えられます。
真上からそのまま下に降りてくる 一つ右から線を伝ってくる
・真上からそのまま下に降りてくる
真上からそのまま下に降りてくるには
一番左の縦棒と右の縦棒を繋ぐ線がなければ
そのまま下に降りてくることができます。
bit探索で導く、パターンを見てみると
左から右に横棒が伸びていないパターンの数は
以下の2つであることが分かります。
×○ ××
そのため、このパターンは
すぐ上の1通り×2パターン=2パターン
となります
・一つ右から線を伝ってくる
一つ右から線を伝ってくるには
一番左の縦棒と一つ右の縦棒の間に
横棒が引かれていることが条件となります。
bit探索で導く、パターンを見てみると
左から右に横棒が伸びているパターンの数は
以下の1つであることが分かります。
○×
そのため、このパターンは
すぐ上の0通り×1パターン=0パターン
となります
これを先ほど出した
すぐ上からくるパターンと足して
答えは2+0=2パターンとなります
*真ん中の赤い点
真ん中の点に到達するには、
以下の3パターン方法が考えられます。
一つ左から線を伝ってくる 真上からそのまま下に降りてくる 一つ右から線を伝ってくる
・一つ左から線を伝ってくる
一つ左から線を伝ってくるには
一番左の縦棒と真ん中の縦棒の間に
横棒が引かれていることが条件となります。
bit探索で導く、パターンを見てみると
左から真ん中に横棒が伸びているパターンの数は
以下の1つであることが分かります。
○×
そのため、このパターンは
すぐ右上の1通り×1パターン=1パターン
となります
・真上からそのまま降りてくる
真上からそのまま降りてくるには
一つ左の縦棒と真ん中の縦棒の間、
そして、一つ右の縦棒と真ん中の縦棒の間に
横棒が引かれていないことが条件となります。
bit探索で導く、パターンを見てみると
どちらにも線が引かれていないパターンの数は
以下の1つであることが分かります。
××
そのため、このパターンは
真上の0通り×1パターン=0パターン
となります
・一つ右から線を伝ってくる
一つ右から線を伝ってくるには
一つ右の縦棒と真ん中の縦棒の間に
横棒が引かれていることが条件となります。
bit探索で導く、パターンを見てみると
右から真ん中に横棒が伸びているパターンの数は
以下の1つであることが分かります。
×○
そのため、このパターンは
すぐ左上の0通り×1パターン=0パターン
となります
以上で出した
3つのパターンをすべて足した
1+0+0=1通りが
1行目真ん中の赤い点の到達パターンとなります。
*一番右の赤い点
一番左の点に到達するには、
以下の2パターン方法が考えられます。
真上からそのまま下に降りてくる 一つ左から線を伝ってくる
・真上からそのまま下に降りてくる
真上からそのまま下に降りてくるには
一番右の縦棒と、一つ左の縦棒を繋ぐ線がなければ
そのまま下に降りてくることができます。
bit探索で導く、パターンを見てみると
左から一番右に横棒が伸びていないパターンの数は
以下の2つであることが分かります。
○× ××
そのため、このパターンは
すぐ上の0通り×2パターン=0パターン
となります
・一つ左から線を伝ってくる
一つ左から線を伝ってくるには
一番右の縦棒と一つ左の縦棒の間に
横棒が引かれていることが条件となります。
bit探索で導く、パターンを見てみると
左から右に横棒が伸びているパターンの数は
以下の1つであることが分かります。
×○
そのため、このパターンは
すぐ左上の0通り×1パターン=0パターン
となります
これを先ほど出した
真上からくるパターンと足して
答えは0+0=0パターンとなります
④2行目以降の行
1行目でしたこと
(一つ上の行と、bit全探索で出した横棒のパターンを組み合わせて、パターンの数を出していく)を
繰り返して下の行へ進んでいきます
動的計画法の部分のコードは以下です
各地点のパターンの値を
二重配列(ansArray[])に保存しながら、下に進んでいます。
bitCountは横棒のパターン全体の値、
arrayH[W-1]には、各地点に横棒があるパターンがいくつあるかの値が入っています。
W-1は横棒の数なので、縦棒の数W-1
H=3であれば以下のようになります
横棒があるを○、横棒がないを×とします
○× ×○ ××
bitCount=3 //パターン全体の数
arrayH={1,1} //横棒がある数 左に一つ、右に一つ
//動的計画法 //各ポイントにおいて何通りのパターンがあるかを保存し、 //それを利用しつつ下へ下る //保存する器を用意 //H横棒の数、いま行でどこにいるか、0~H //W横棒の数、いま列でどこにいるか、0~W-1 var ansArray = new long[H+1,W]; //行のループ for (int i=0;i<=H;++i) { //列のループ for (int j=0;j<W;++j) { if (i == 0) { //0,0地点は始点=1 if (j == 0) ansArray[i, j] = 1; else ansArray[i, j] = 0; } //列が0のとき(一番左端) else if (j==0) { //真上 var temp = (ansArray[i - 1, j] * (bitCount-arrayH[0])) % Mod; //右 temp = (temp + (ansArray[i - 1, j + 1] * arrayH[0])) % Mod; ansArray[i, j] = temp; } //列がW-1のとき(一番右端) else if (j == W - 1) { //真上 var temp = (ansArray[i - 1, j] * (bitCount - arrayH[W-2])) % Mod; //左 temp = (temp + (ansArray[i - 1, j - 1] * arrayH[W-2])) % Mod; ansArray[i, j] = temp; } //それ以外 else { //真上 var temp = (ansArray[i - 1, j] * (bitCount - ( arrayH[j-1] + arrayH[j]) )) % Mod; //左 temp = (temp + (ansArray[i - 1, j - 1] * arrayH[j - 1] )) % Mod; //右 temp = (temp + (ansArray[i - 1, j + 1] * arrayH[j])) % Mod; ansArray[i, j] = temp; } } }
2.bit全探索
一つの行において、
あみだくじの横棒のあるなしのパターンを考える
例えば、
縦棒の数が3であれば、
横棒の入る可能性のある隙間は二つある。
また、問題文から
同じ行に横棒が二つ連続で並ぶことはないので
横棒があるを○、横棒がないを×とすると
横棒のパターンは以下のようになる
○× ×○ ××
(○○は横棒が二つ並んでいて、正式なあみだくじにならないので省く)
この組み合わせのパターンを出すために
bit全探索を使用する。
bit全探索は集合の部分集合を出してくれる。
様々なところで解説されているので
ここでの解説は割愛する。
以下の記事が分かり易い。
lovedvoraklayout.hatenablog.com
このbit全探索で吐き出されたものから
線が二つ連続で続くものを省き
さらに後の全探索で
横棒の線の有無の情報を使用したいので保存しておく。
(上のコードのbitCount(横棒の有無の全パターン)と
arrayH[W-1](各場所において横棒の有無を、保存しているリスト))
bit全探索部分のコード
//ビット探索 //横の線のあるなしを全列挙する var bitList = new List<string>(); for (int i=0;i<(1<<(W-1));++i) { //二進数に変換 var value=Convert.ToString((i), 2); //空いている桁は0埋めする var bit =value.PadLeft(W-1,'0'); //横棒が二つ続いた場合、処理をスキップさせるためのフラグ var isContinue = true; //横棒が二つ続くことはないので、その場合を除く for (int j=0;j<W-2;++j) { if (bit[j] == '1' && bit[j + 1] == '1') { isContinue = false; break; } } //横棒が二つ続かないパターン(正当なあみだくじ) if (isContinue) { bitList.Add(bit); for (int j=0;j<W-1;++j) if (bit[j] == '1') arrayH[j]++; } }
bitListはこの後、bitCount(パターンすべての値)を
出すためにしか使っていないので
値をリストに保存する必要はないです。
全体のコード
using System; using System.Linq; using System.Collections.Generic; class Dmondai { static void Main() { const long Mod= 1000000007; var line=Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray(); var H = line[0]; var W = line[1]; var K = line[2]; //縦棒が一つしかない場合は1 if (W == 1) { Console.WriteLine(1); return; } //それぞれの位置の横棒の数を保存する var arrayH = new long[W-1]; //ビット探索 //横の線のあるなしを全列挙する var bitList = new List<string>(); for (int i=0;i<(1<<(W-1));++i) { //二進数に変換、 var value=Convert.ToString((i), 2); //空いている桁は0埋めする var bit =value.PadLeft(W-1,'0'); //横棒が二つ続いた場合、処理をスキップさせるためのフラグ var isContinue = true; //横棒が二つ続くことはないので、その場合を除く for (int j=0;j<W-2;++j) { if (bit[j] == '1' && bit[j + 1] == '1') { isContinue = false; break; } } //横棒が二つ続かないパターン(正当なあみだくじ) if (isContinue) { bitList.Add(bit); for (int j=0;j<W-1;++j) if (bit[j] == '1') arrayH[j]++; } } //ビットりすと内にある数を保存(横棒のパターン) long bitCount = bitList.Count(); //動的計画法 //各ポイントにおいて何通りのパターンがあるかを保存し、 //それを利用しつつ下へ下る //保存する器を用意 //H横棒の数、いま行でどこにいるか、0~H //W横棒の数、いま列でどこにいるか、0~W-1 var ansArray = new long[H+1,W]; //行のループ for (int i=0;i<=H;++i) { //列のループ for (int j=0;j<W;++j) { if (i == 0) { //0,0地点は始点=1 if (j == 0) ansArray[i, j] = 1; else ansArray[i, j] = 0; } //列が0のとき else if (j==0) { //真上 var temp = (ansArray[i - 1, j] * (bitCount-arrayH[0])) % Mod; //右 temp = (temp + (ansArray[i - 1, j + 1] * arrayH[0])) % Mod; ansArray[i, j] = temp; } //列がW-1のとき(一番右端) else if (j == W - 1) { //真上 var temp = (ansArray[i - 1, j] * (bitCount - arrayH[W-2])) % Mod; //左 temp = (temp + (ansArray[i - 1, j - 1] * arrayH[W-2])) % Mod; ansArray[i, j] = temp; } //それ以外 else { //真上 var temp = (ansArray[i - 1, j] * (bitCount - ( arrayH[j-1] + arrayH[j]) )) % Mod; //左 temp = (temp + (ansArray[i - 1, j - 1] * arrayH[j - 1] )) % Mod; //右 temp = (temp + (ansArray[i - 1, j + 1] * arrayH[j])) % Mod; ansArray[i, j] = temp; } } } Console.WriteLine(ansArray[H,K-1]); } }