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通りになる

○×
×○
××

動的計画法を用いて、それぞれの地点におけるパターンの数を出す
f:id:aoaoaoaoaoaoaoi:20181124161758p:plain
入力よりH=2、K=3なので
答えは右下の点となり1通り(詳細は下で解説)

ここから詳しく解説していく
解いていく順序としては逆だが
bit全探索時に
何の情報を保存すればよいのかが分かり易くなるため、
動的計画法から解説していく。

1.動的計画法

まず、動的計画法とは
通過点の値を保存し、
利用しながら先に進んでいく方法です
文章で説明すると難しいので、以下問題を解きながら解説していきます

今回のあみだくじの例でいえば、
ゴールがKの示す部分(黄緑色の丸がついている部分)、
通過点はあみだくじの各地点(赤い点がついている部分)です
以下、H=2、K=3の図
f:id:aoaoaoaoaoaoaoi:20181124161758p:plain
この各赤い地点の値を出しつつ、
上から下へ向かい
Kというゴールを目指します。

それでは、以下手順です。
入力は「2 3 3」を想定しています。
bit探索で出す以下のパターンを使用します。
横棒があるを○、横棒がないを×とします

○×
×○
××

①スタート地点
問題文から、スタート地点は、一番左上の赤い点です
この点に来るのは「一番初め」以外にはあり得ないので
この地点に来れるのは「1通り」だけです
f:id:aoaoaoaoaoaoaoi:20181124171000p:plain
②0番上の行
スタート地点である
一番左以外の赤い点は到達することはできないので
全て0通りとなります
f:id:aoaoaoaoaoaoaoi:20181124172348p:plain
③1番目の行
*一番左の赤い点
一番左の点に到達するには、
以下の2パターン方法が考えられます。

真上からそのまま下に降りてくる
一つ右から線を伝ってくる

・真上からそのまま下に降りてくる
真上からそのまま下に降りてくるには
一番左の縦棒と右の縦棒を繋ぐ線がなければ
そのまま下に降りてくることができます。
bit探索で導く、パターンを見てみると
左から右に横棒が伸びていないパターンの数は
以下の2つであることが分かります。

×○
××

そのため、このパターンは
すぐ上の1通り×2パターン=2パターン
となります

・一つ右から線を伝ってくる
一つ右から線を伝ってくるには
一番左の縦棒と一つ右の縦棒の間に
横棒が引かれている
ことが条件となります。
bit探索で導く、パターンを見てみると
左から右に横棒が伸びているパターンの数は
以下の1つであることが分かります。

○×

そのため、このパターンは
すぐ上の0通り×1パターン=0パターン
となります
これを先ほど出した
すぐ上からくるパターンと足して
答えは2+0=2パターンとなります
f:id:aoaoaoaoaoaoaoi:20181124175044p:plain

*真ん中の赤い点
真ん中の点に到達するには、
以下の3パターン方法が考えられます。

一つ左から線を伝ってくる
真上からそのまま下に降りてくる
一つ右から線を伝ってくる

・一つ左から線を伝ってくる
一つ左から線を伝ってくるには
一番左の縦棒と真ん中の縦棒の間に
横棒が引かれている
ことが条件となります。
bit探索で導く、パターンを見てみると
左から真ん中に横棒が伸びているパターンの数は
以下の1つであることが分かります。

○×

そのため、このパターンは
すぐ右上の1通り×1パターン=1パターン
となります

・真上からそのまま降りてくる
真上からそのまま降りてくるには
一つ左の縦棒と真ん中の縦棒の間、
そして、一つ右の縦棒と真ん中の縦棒の間に
横棒が引かれていない
ことが条件となります。
bit探索で導く、パターンを見てみると
どちらにも線が引かれていないパターンの数は
以下の1つであることが分かります。

××

そのため、このパターンは
真上の0通り×1パターン=0パターン
となります

・一つ右から線を伝ってくる
一つ右から線を伝ってくるには
一つ右の縦棒と真ん中の縦棒の間に
横棒が引かれている
ことが条件となります。
bit探索で導く、パターンを見てみると
右から真ん中に横棒が伸びているパターンの数は
以下の1つであることが分かります。

×○

そのため、このパターンは
すぐ左上の0通り×1パターン=0パターン
となります
以上で出した
3つのパターンをすべて足した
1+0+0=1通りが
1行目真ん中の赤い点の到達パターンとなります。
f:id:aoaoaoaoaoaoaoi:20181124180418p:plain

*一番右の赤い点
一番左の点に到達するには、
以下の2パターン方法が考えられます。

真上からそのまま下に降りてくる
一つ左から線を伝ってくる

・真上からそのまま下に降りてくる
真上からそのまま下に降りてくるには
一番右の縦棒と、一つ左の縦棒を繋ぐ線がなければ
そのまま下に降りてくることができます。
bit探索で導く、パターンを見てみると
左から一番右に横棒が伸びていないパターンの数は
以下の2つであることが分かります。

○×
××

そのため、このパターンは
すぐ上の0通り×2パターン=0パターン
となります

・一つ左から線を伝ってくる
一つ左から線を伝ってくるには
一番右の縦棒と一つ左の縦棒の間に
横棒が引かれている
ことが条件となります。
bit探索で導く、パターンを見てみると
左から右に横棒が伸びているパターンの数は
以下の1つであることが分かります。

×○

そのため、このパターンは
すぐ左上の0通り×1パターン=0パターン
となります
これを先ほど出した
真上からくるパターンと足して
答えは0+0=0パターンとなります
f:id:aoaoaoaoaoaoaoi:20181124181953p:plain

④2行目以降の行
1行目でしたこと
(一つ上の行と、bit全探索で出した横棒のパターンを組み合わせて、パターンの数を出していく)を
繰り返して下の行へ進んでいきます
f:id:aoaoaoaoaoaoaoi:20181124182750p:plain

動的計画法の部分のコードは以下です
各地点のパターンの値を
二重配列(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]);
 
    }
}