TopCoder SRM 532 Div1 Medium DengklekBuildingRoads

この問題は割とあっさり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=11767

問題

数値N,M,Kが与えられる。
1～N番の頂点が並んでいるので、この時M本の辺を張ったグラフを作りたい。
この時、以下の条件を満たすグラフの数を求めよ。

• 各辺が結ぶ２頂点は、数値の差がK以下であること。
• 各頂点に張られる辺の数は偶数であること。

解法

Kが小さいことを利用して、近傍K頂点の辺の偶奇をbitmapで保持してDPすればよい。
DPの状態は[今の頂点番号][残り辺の数][今より先K個先までの頂点の辺の偶奇]でN*M*2^K通りである。

実際はDPを２回行う。
１回目で、「今からi番目までの頂点の間にある本数の辺を張ったときにあるbitmapを生成する組み合わせ」を計算する。
２回目で、１回目の結果を使って[今の頂点番号][残り辺の数][今より先K個先までの頂点の辺の偶奇]を計算する。

１回目はO(N*M*K*2^K)、２回目はO(N*M^2*2^K)。
N,M,Kはあまり大きくないので十分終わる。

ll mo=1000000007;
ll dpdp[31][31][1<<8];
ll dp1[9][31][1<<8];

class DengklekBuildingRoads {
	public:
	
	int numWays(int N, int M, int K) {
		int i,x,y,mask,mask2;
		
		ZERO(dp1);
		dp1[0][0][0]=1;
		FOR(i,K) {
			FOR(x,31) FOR(y,31) if(x+y<=M) {
				FOR(mask,1<<K) {
					dp1[i+1][x+y][mask ^ ((y%2)<<i)] += dp1[i][x][mask];
					dp1[i+1][x+y][mask ^ ((y%2)<<i)] %= mo;
				}
			}
		}
		
		ZERO(dpdp);
		dpdp[0][M][0]=1;
		
		FOR(i,N) {
			int l = min(K,N-i-1);
			FOR(mask,1<<K) FOR(y,M+1) if((mask%2)==(y%2)) {
				for(x=y;x<=M;x++) if(dpdp[i][x][mask]) {
					FOR(mask2,1<<l) if(dp1[l][y][mask2]) {
						dpdp[i+1][x-y][mask2 ^ (mask>>1)] += dpdp[i][x][mask] * dp1[l][y][mask2];
						dpdp[i+1][x-y][mask2 ^ (mask>>1)] %= mo;
					}
				}
			}
		}
		
		return dpdp[N][0][0];
	}
};

まとめ

割とオーソドックスなDP問題。