SRM722 Lv3 : DominoTiling

作成日:2017.10.13
最終更新日:2017.10.13

問題概要

問題本文

 $H \times W$の$grid$が与えられる。 $'X'$のマスには障害物があり、$'.'$のマスにはない。 障害物がないマスを$2 \times 1$のドミノ(向きは任意)で覆う時の覆い方を求めよ。
制約
$1 \leq H,W \leq 12$

考え方

 上の行からドミノの置き方を決めていくことを考える。 ドミノの大きさは$2 \times 1$であるから、ある行のドミノの置き方はその行に隣接する行にのみ依存する。 そこで、行をまたぐ置き方とまたがない置き方で分けて考える。 前者は後者を決めれば$0$通りか$1$通りに定まることから、後者を決めてから下の行に移るということをすれば良さそうである。 これは各行の空きマスの状態それぞれにおいて、その状態になる置き方の数を保持するbitDPで実現できる。 すなわち、ドミノを行をまたがないように左から順に置いていった後、行をまたぐようにドミノを置くことで空きマスを埋めていくことを行ごとに繰り返していけば良い。 計算量は$O(HW2^W)$なので十分高速である。

ソースコード

マクロ等はこちら

class DominoTiling {
	int bit[16];
	LL dp[16][1<<16];
public:
	long long count(vector<string> grid) {
		int H = grid.size();
		int W = grid[0].size();
		repp(i,0,H){
			bit[i] = (1<<W)-1;
			repp(j,0,W){
				if(grid[i][j] == 'X') bit[i] -= (1<<j);
			}
		}
		bit[H] = (1<<W)-1;
		dp[0][bit[0]] = 1;
		repp(i,0,H){
			repp(j,1,W){
				repp(k,0,1<<W){
					if((k&(1<<(j-1))) == 0 || (k&(1<<j)) == 0) continue;
					dp[i][k-(1<<(j-1))-(1<<j)] += dp[i][k];
				}
			}
			if(i==H-1) break;
			repp(k,0,1<<W){
				if((k&bit[i+1]) != k) continue;
				dp[i+1][bit[i+1]^k] = dp[i][k];
			}
		}
		return dp[H-1][0];
  	}
};

解法まとめ

 bitDPを行う。
 まず行をまたがないようにドミノを左から順に置いていく。(17-22行)
 その後、空きマスすべてを下の行にまたがるようにドミノを置くことで埋める。(24-27行)

SRM722の他の問題 Lv1 Lv2

広告

自己紹介

プログラミングとかUTAUとかドット絵とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告