TopCoder SRM 590 Div2 Hard FoxAndShogi

チェス・囲碁と来て最後は将棋。
http://community.topcoder.com/stat?c=problem_statement&pm=12745

問題

将棋盤の上にいくつか上向きまたは下向きの歩がある。
それぞれの歩は進行方向に他の歩がいない場合、１マス動くことができる。
初期状態から遷移できる将棋盤の状態数を答えよ。

解法

列単位は独立しているので、各列の結果を掛け合わせればよい。

各列はDPすればよい。
上の行から順に見て、X行目にある歩がY行目に移動した場合、というのを累積していく。
下向きならY>=Xでないといけないし、上向きならY<=Xでないといけない。
また、X行目より上にある歩がZ行目に移動しているなら、Y>Zでないといけない。

O(N^4)なので何とか間に合う。

ll mo=1000000007;
ll dp[52][52];
class FoxAndShogi {
	int N;
	public:
	
	ll numpat(string S) {
		int i,x,y;
		ZERO(dp);
		dp[0][0]=1;
		
		FOR(i,N) {
			ZERO(dp[i+1]);
			if(S[i]=='.') memmove(dp[i+1],dp[i],sizeof(dp[i]));
			else if(S[i]=='D') for(x=i+1;x<=N+1;x++) FOR(y,x) dp[i+1][x] += dp[i][y];
			else if(S[i]=='U') for(x=1;x<=i+1;x++) FOR(y,x) dp[i+1][x] += dp[i][y];
			FOR(x,N+1) dp[i+1][x] %= mo;
		}
		ll r=0;
		FOR(i,N+1) r+=dp[N][i];
		return r;
	}
	
	
	int differentOutcomes(vector <string> board) {
		N=board.size();
		ll ret=1;
		int i,j;
		FOR(i,N) {
			string S;
			FOR(j,N) S+=board[j][i];
			ret = (ret * numpat(S)) % mo;
		}
		return (int)ret;
	}

};

まとめ

最初どうDP組むか迷ったけど、方針決まったらすぐできた。
TDPCの成果…だといいなぁ。