UAPC2014 D Draw Puzzle

AOJ 動的計画法

問題

図があるので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2014Day1&pid=D）
3xnのグリッドに4種類のピースを当てはめて、格子点を結ぶパスを作る。
ピースa, b, c, dがa枚b枚c枚d枚使えるとき
グリッドの左端の格子点から右端の格子点までのパスを描くことができるか。

制約条件

n≦30
a, b, c, d≦10

方針

DP.
3行しかないので、x座標で2歩以上戻ることはない。
つまり、一列ずつピースの選び方を試していけばよい。


dp[x座標][y座標][a][b][c][d]として、
一列ずつピースの当てはめ方125通りを全部試す。
愚直にやるとTLEなので、前処理を頑張る。
はじめに125通りに対して、何行目から何行目までいけるかのテーブルを作る。


テーブルを作ったら、当てはめ方のうち無駄なものを削除する。
i行目からj行目までいくのに使う当てはめかたのうち、

  • 別の当てはめ方でi行目からj行目までいける
  • しかもその当てはめ方は、使う場所が一緒（か部分集合になっている）
  • 使うピースの枚数が少なくて済む

ような別の当てはめ方があるものは完全に無駄なので考えなくてよい。


これをすると、遷移がたった20通りくらいになる。
なので計算量は4 * 30 * 10 * 10 * 10 * 10 * 20くらいで、
2000万ちょいくらいになる。実際にはいけない状態もかなりあるので、ジャッジ上で0.03sくらい。

ソースコード

bool can[125][8][8];
bool tile[4][2][2] = {
	{{1, 0}, {0, 0}},
	{{0, 0}, {0, 1}},
	{{0, 0}, {1, 0}},
	{{0, 1}, {0, 0}}
};

int w, a, b, c, d;
bool dp[33][4][11][11][11][11];
string in[3];

int main(){
	vi bits[4][4];
	rep(bit, 125){
		int tmp = bit;
		rep(i, 3){
			int t = tmp % 5; tmp /= 5;
			if(t == 4) continue;
			rep(j, 2) rep(k, 2) if(tile[t][j][k])
			can[bit][i + j][i + k + 4] = can[bit][i + k + 4][i + j] = 1;
		}
		rep(k, 8) rep(i, 8) rep(j, 8) can[bit][i][j] |= can[bit][i][k] && can[bit][k][j];
	}
	
	rep(f, 4) rep(to, 4) rep(b1, 125) if(can[b1][f][to + 4]){
		bool ok = 1;
		rep(b2, 125){
			if(b1 == b2 || !can[b2][f][to + 4]) continue;
			int cnt[4] = {};
			int tmp = b1, f1 = 0, f2 = 0;

			rep(i, 3){
				int t = tmp % 5; tmp /= 5;
				if(t < 4) cnt[t]--, f1 |= 1 << i;
			}
			tmp = b2;
			rep(i, 3){
				int t = tmp % 5; tmp /= 5;
				if(t < 4) cnt[t]++, f2 |= 1 << i;
			}
			if((f1 & f2) == f2 && cnt[0] <= 0 && cnt[1] <= 0 && cnt[2] <= 0 && cnt[3] <= 0){
				ok = 0;
				break;
			}
		}
		if(ok) bits[f][to].pb(b1);
	}
	
	cin >> w;
	rep(i, 3) cin >> in[i];
	cin >> a >> b >> c >> d;
	
	rep(i, 4) dp[0][i][a][b][c][d] = 1;
	rep(i, w) rep(j, 4) rep(a, 11) rep(b, 11) rep(c, 11) rep(d, 11) if(dp[i][j][a][b][c][d]){
		
		rep(to, 4) rep(bt, bits[j][to].size()){
			int bit = bits[j][to][bt];
			int na = a, nb = b, nc = c, nd = d, tmp = bit;
			
			rep(k, 3){
				int t = tmp % 5; tmp /= 5;
				if(t < 4 && in[k][i] != 'O') goto FAIL;
				if(t == 0) na--;
				else if(t == 1) nb--;
				else if(t == 2) nc--;
				else if(t == 3) nd--;
			}
			if(na < 0 || nb < 0 || nc < 0 || nd < 0) continue;
			
			dp[i + 1][to][na][nb][nc][nd] = 1;
			FAIL:;
		}
	}
	rep(i, 4) rep(a, 11) rep(b, 11) rep(c, 11) rep(d, 11) if(dp[w][i][a][b][c][d]){
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	
	return 0;
}