TopCoder SRM 557 Div2 Hard FoxAndMountain

Div2の問題だけど、Div1 Easyと同じような問題でこちらの方が難しそうなので試してみた。
http://community.topcoder.com/stat?c=problem_statement&pm=11810

先のDiv1 Easyと似た問題。
n<=50、h[0]=h[n]=0と条件が緩和された一方、求めるのは到達可否だけじゃなくて到達方法の組み合わせ数。

最初は、通るべきパターンを１か所に置き、そのパターンに入るまでとパターンの後の数を掛けて累積したが、それだと数が大きすぎてダメだった。
というのも、パターンを２回以上通るケースを二重にカウントしてしまうため。

そこで戦略を変更。
まず、パターンのうちi文字目までたどったとき、次にUまたはDが来たとき、パターンの何文字目にくるかの遷移図(下記trans)を作る。
パターンが"UUUDUUUDD"なら、7文字目までたどったときに8文字目が"D"なら8、"U"なら5("UUUDUUUDU"はパターンの先頭8文字と一致しないが、最後5文字の"UUUDU"はパターンの先頭5文字に一致するから)
１回パターンをたどりきってしまえば、あとはUでもDでもパターンを辿りきった状態を繰り返す。

あとは、たどった数列の数・パターンの文字数・現在の高さ、の３つの要素でDPする。
最後に高さが0で、かつパターンを辿りきった数を答える。

class FoxAndMountain {
	public:
	int trans[51][2];
	int memo[51][51][51];
	static const int mo=1000000009;
	
	
	int count(int n, string history) {
		int hl, mind,h,i,j,k,res;
		char tstr[51];
		char sstr[51];
		
		hl = history.size();
		strcpy(sstr,history.c_str());
		
		ZERO(trans);
		
		
		FOR(i,hl) {
			//_P("%d %d\n",trans[i][1],trans[i][0]);
			ZERO(tstr);
			memmove(tstr,history.c_str(),i);
			if(history[i]=='U') {
				trans[i][1]=i+1;
				tstr[i]='D';
				for(j=1;j<=i;j++) {
					if(memcmp(sstr,&tstr[i-(j-1)],j)==0) trans[i][0]=j;
				}
			}
			else {
				trans[i][0]=i+1;
				tstr[i]='U';
				for(j=1;j<=i;j++) {
					if(memcmp(sstr,&tstr[i-(j-1)],j)==0) trans[i][1]=j;
				}
			}
		}
		trans[hl][0]=trans[hl][1]=hl;
		
		ZERO(memo);
		memo[0][0][0]=1;
		FOR(i,n) {
			FOR(j,26) {
				FOR(k,hl+1) {
					if(memo[i][j][k]==0) continue;
					if(j>0){
						memo[i+1][j-1][trans[k][0]] += memo[i][j][k];
						memo[i+1][j-1][trans[k][0]] %= mo;
					}
					if(j<25) {
						memo[i+1][j+1][trans[k][1]] += memo[i][j][k];
						memo[i+1][j+1][trans[k][1]] %= mo;
					}
				}
			}
		}
		
		return memo[n][0][hl];
	}
}

まとめ

ヒント無しで解き切れたので良かった。
でもこれ、本番の時間内じゃ解けないな。

１か所はまったのが、一部「//遷移表」というコメントを入れたら文字コードの都合で次の行までコメントアウトされてしまい、デバッグに手こずった。
日本語コメント入れるときは気を付けよう…。