会津合宿2012 1日目 F問題 Transparent Mahjong

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2012Day1&pid=F）。

麻雀牌が3n + 1枚あって、いくつかは*で見えない。
このとき、あたり牌として可能性のあるものは何か、全て出力する。

ただし、同じ牌は4枚までしか存在しないものとする。
麻雀牌は1〜12までの数字で表され、数字以外で区別されないものとする。

方針

用語の解説
面子：　1 2 3や2 2 2などの、3枚の牌の組
雀頭：　4 4などの2枚の牌のペア

この問題では、上がり形で面子n個と雀頭1個が出来ている必要がある。

まずは雀頭と、上がり牌を決め付ける（12 * 12通り試す）。
その上で動的計画法により、それぞれに対して、*の牌をちゃんと上がり形に割り当てられるかを確認する。

動的計画法は以下の通り。
dp[i][a][b][k]
iの数字の牌まで見ていて、
iの数字の牌を、直前までの面子によりa枚使っていて、
i+1の数字の牌を直前までの面子によりb枚使っていて、
k枚 * の牌が残っているときような場合に至れるかどうかとして、

ここからiの数字の牌を開始点とする階段i i + 1 i + 2をいくつ作るか、
iの数字3つ組を作るかでループをまわしてテーブルを更新する。

牌が足りなくなったり、余ったりしたらその更新は不可能にする。

ソースコード

int n, a[20], b, m[20], k;
bool dp[20][5][5][60];

bool ok(int atari, int atama){
	
	rep(i, 20) m[i] = a[i];
	m[atari]++;
	if(m[atama] + b < 2) return 0;
	
	int t = max(0, 2 - m[atama]);
	m[atama] -= 2 - t;
	k = b - t;
	
	memset(dp, 0, sizeof(dp));
	
	dp[1][0][0][k] = 1;
	for(int i = 1; i < 13; i++)
	rep(a, 5) rep(b, 5) rep(w, k + 1) if(dp[i][a][b][w]){
		
		rep(s, 5) rep(ko, 2){
			if(a + s + ko * 3 > (i == atama ? 2 : 4)) continue;
			if(a + s + ko * 3 < m[i]) continue;
			
			int use = a + s + ko * 3 - m[i];
			if(use < 0 || use > w) continue;
			if(s + b > 4) continue;
			
			dp[i + 1][s + b][s][w - use] = 1;
		}
	}
	return dp[13][0][0][0];
}

int main(){
	cin >> n;
	rep(i, 3 * n + 1){
		string s;
		cin >> s;
		if(s == "*") b++;
		else a[atoi(s.c_str())]++;
	}
	
	bool ans[20] = {};
	for(int i = 1; i < 13; i++) for(int j = 1; j < 13; j++)
	if(ok(i, j)) ans[i] = ans[0] = 1;
	
	if(!ans[0]) cout << -1 << endl;
	else for(int i = 1; i < 13; i++) if(ans[i]) cout << i << endl;
	
	return 0;
}