kmjp's blog

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

TopCoder SRM 573 Div2 Hard WolfPackDivTwo

さてDiv2 Hard。
http://community.topcoder.com/stat?c=problem_statement&pm=12467

問題

N個の点の座標が格子点で与えられる。
ここからMターン各点は隣接する格子点に動く。
Mターン後に全部の点が同じ点にくるような組み合わせの数を答える。

解法

なんか似た問題見たことある…と思ったら、Autumn Festの問Eだ。
移動距離の条件などは違うけどね。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_05


ある点がMターン後に別の点に行くパターンは、上下左右の回数を組み合わせ計算で求めることもできる。
ただ、この組み合わせ計算はめんどい。

ここで上記Automn Fest Eの解説を見ると、「原点からDFSすれば、各点に行くパターン数が求められる」とある。
今回の問題もこれを採用。
原点からMターン後に各点に行く場合の数をDPで計算。

N個の点は(0,0)-(50,50)の内部にあり、M<=50なので、(-50,-50)-(100,100)の点に対し、N個の点がMターン後にたどり着く場合の数を掛け合わせればよい。

ll dp[51][105][105];
ll MO=1000000007;

class WolfPackDivTwo {
	public:
	
	int calc(vector <int> X, vector <int> Y, int m) {
		int n,x,y,i;
		int N=X.size();
		
		ZERO(dp);
		dp[0][52][52]=1;
		
		for(n=1;n<=m;n++) {
			for(x=2;x<=102;x++) for(y=2;y<=102;y++) {
				dp[n][x-1][y]=(dp[n][x-1][y]+dp[n-1][x][y])%MO;
				dp[n][x+1][y]=(dp[n][x+1][y]+dp[n-1][x][y])%MO;
				dp[n][x][y-1]=(dp[n][x][y-1]+dp[n-1][x][y])%MO;
				dp[n][x][y+1]=(dp[n][x][y+1]+dp[n-1][x][y])%MO;
			}
		}
		
		ll pat=0;
		for(x=-50;x<=100;x++) for(y=-50;y<=100;y++) {
			ll tpat=1;
			FOR(i,N) {
				if(abs(X[i]-x)+abs(Y[i]-y)>m) {
					tpat=0;
					break;
				}
				tpat = (tpat * dp[m][52+X[i]-x][52+Y[i]-y]) % MO;
			}
			pat=(pat+tpat)%MO;
		}
		return (int)pat;
	}

};

まとめ

Div2 Hardの割にさっくり解けた問題。
Autumn Festの成果が出たってもんだ。
…残念ながら、問題空間が増えたDiv1 Hardではこれは使えないんだけどね…。