kmjp's blog

競技プログラミング参加記です

Croc Champ 2013 - Round 2 : B. Distinct Paths

ではB。今回CよりBの方が正答者少ないね。
http://codeforces.com/contest/293/problem/B

問題

マス目上に0~Nの数字が書かれている。
このうち0の部分を1~Nのいずれかで置き換え、左上から右下に1マスずつ移動した場合、どんなルートであっても同じ数字を2回辿らないようにしたい。
そのような置き換え方の組み合わせ数を答えよ。

解法

まず、条件より明らかに(幅)+(高さ)-1<=Nである。
N<=10と小さいので、最もマスが多い場合でも幅と高さが5と6の場合になる。
あとは、左上から右下まで1~Nを実際に割り振りを全パターン行い、かつすでに1~Nの数が埋まってる場所と矛盾しないかチェックすればよい。

この際、2つほど最適化を加えてTLEを回避した。

  • マス目全体の数値を入れ替えただけの計算を高速化するため、まずは左上からDFSする際に1から順に仮数値を割り当て、最後にその仮数値の組み合わせ数を掛けることで入れ替え分を何度もDFSすることを防ぐ。
  • これでも最大の30マスの際はTLEする。ここで、(幅)+(高さ)-1==Nの場合は割り当て方は(数字の入れ替えを除くと)1パターンしかないので、他の割り当てを省略する。25マスなでこの処理はなくても間に合う。
int H,W,K,unfixed;
int A[1001][1001];
int UM[11][11];
int V[11][11];

ll P[11][11];
ll mo=1000000007;

int count(int nk){
	int as[11];
	int y,x,nf;
	ZERO(as);
	FOR(y,H) FOR(x,W) if(A[y][x]!=0) {
		if(as[V[y][x]]!=0 && as[V[y][x]]!=A[y][x]) return 0;
		as[V[y][x]]=A[y][x];
	}
	FOR(x,nk) for(y=x+1;y<nk;y++) if(as[x+1] && as[y+1] && as[x+1]==as[y+1]) return 0;
	nf=0;
	FOR(x,nk) if(as[x+1]) nf++;
	return P[K-nf][nk-nf];
}

ll dfs(int x,int y,int nk) {
	int i;
	ll sum=0;
	
	UM[y][x]=0;
	if(y>0) UM[y][x]|=UM[y-1][x];
	if(x>0) UM[y][x]|=UM[y][x-1];
	
	int ny,nx;
	nx=x+1;
	ny=y-1;
	if(ny<0 || nx>=W) {
		nx=0;
		ny=x+y+1;
	}
	while(ny>=H) ny--,nx++;
	
	for(i=1;i<=min(K,nk+1);i++) {
		if(UM[y][x]&(1<<i)) continue;
		if(W+H-1==K && i!=x+y+1) continue;
		
		UM[y][x] |= 1<<i;
		V[y][x]=i;
		
		if(x==W-1 && y==H-1) sum+=count(nk+(i==(nk+1)));
		else sum+=dfs(nx,ny,nk+(i==(nk+1)));
		sum%=mo;
		
		UM[y][x] ^= 1<<i;
	}
	return sum;
	
}

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	H=GETi();
	W=GETi();
	K=GETi();
	FOR(y,H) FOR(x,W) A[y][x]=GETi();
	
	if(H+W-1>K) {
		_P("0\n");
		return;
	}
	
	for(x=0;x<=10;x++) {
		P[x][0]=1;
		FOR(y,x) P[x][y+1]=(P[x][y]*(x-y))%mo;
	}
	
	ZERO(UM);
	cout << dfs(0,0,0) << endl;
	return;
}

まとめ

同じ処理の再計算を防ぐため、ユニークな組み合わせだけ求めて、数値の入れ替えは簡単な計算で済ます、というテクは今後も使えそうだ。