atcoder ABC113 D問題

3430 ワード
AtCoder java8 AtCoder テキストリンク

今回はビット全探索とdpを組み合わせた問題でありとても難しかった。
https://atcoder.jp/contests/abc113/tasks/abc113_d

方針

あみだくじをもとに、好きに横棒を配置し、指定した位置にくるようにできる横棒の配置の組み合わせを数え上げる問題である。あみだくじの性質上、横棒は水平なので、ある高さをhとし、左からw列目について考えると、h-1から(h,w)にくるのは、3通り
(1) 高さh-1でw列とw-1列が繋がっている時

(2) 高さh-1でw列とw+1列が繋がっている時

(3) (1)(2)以外(真上から降りてくる時)

つまり、それぞれの高さについて横棒の置き方を全列挙して、(1)~(3)の場合分けをしてdpを更新していくことで、目的の高さH、K列目の総数を求めることができる。ここで問題となるのが、横棒の全列挙の仕方であるがここではビット全探索を用いる。

ビット全探索とは

ビット演算を用いて、横棒を表すものである。根本的な考え方としては、ビット演算は二進数で考えるので、01を左に1ビットする(1に2をかける)と10(2)となる。つまり,0001の1を横棒で表そうということである。ここで、

for(int i = 0;i < (1 << W-1);i++){

}

のようにすると、0001,0010,0011,0100,0101,.....のようにw番目まで全通り二進数で表せる。つまり横棒の組み合わせを全列挙できる。ここで、問題文をみると、横が繋がるのは禁止されている。図で見ると以下の感じ。
なので、このような配置は取り除かなければならない。ここで、横棒を二進数の1で表したことを考え、横でつながっているのを11で表せば良いと気づく。なので、ある配置(例えば01010)に対し、(00011,00110,01100,11000)のように11を左から右へスライドしていき、ビット論理積(&)を取り、11をスライドしたものと同じになるかどうかで、横棒が繋がっているか判定できる。
例えばある配置が(10011)の時、00011と論理積を取ると

例
System.out.print(11 & 3)   // 10011 & 00011
結果
3                         //00011

となる。

引用、参考
http://lovedvoraklayout.hatenablog.com/entry/bit-full-searchhttp://kaworu.jpn.org/kaworu/2008-04-10-2.php