UTPC2012 : G - k番目の文字列

うーん、これも自前で解こうと思ったけど無理だった。
http://utpc2012.contest.atcoder.jp/tasks/utpc2012_07

'a'から連続するN個のアルファベットを１個ずつ使う文字列に対し、全部分文字列を辞書順に並べたとき、K番目が与えられた文字列になる文字列の数を答える問題。
DPを使うんだろうと思ったけど、どうDPすればいいかわかんなかった。

ここは解説を見てチャレンジ。

与えられた文字列の先頭文字より辞書順で前の文字がM個目にある場合、その文字で始まる文字列が(N+1)-M個ある。
与えられた文字列長がLの時、先頭文字より辞書順で前の文字列をうまく配置して、K-L個の部分文字列ができるようにすればよい。

先に与えられた文字列を１か所配置し、残りの(N-L)個からそのような文字の配置の個数をDPで選ぶ。
また、先頭文字より前の文字の数の並べ替え方と、後の文字の並べ替え方をそれぞれ階乗計算して数え上げればよい。

int N,K,L,M;
char str[30];


void solve() {
	int x,y,i,j,rr,TM,nc;
	int tx,ty;
	int dp[27][27][500];
	ll p,cch;
	
	N=GETi();
	K=GETi();
	GETs(str);
	
	L=strlen(str);
	M=str[0]-'a';
	FOR(i,L) if(str[i]<str[0]) M--;
	
	p=0;
	FOR(x,N-L+1) {
		int cp=K-L;
		FOR(i,L) if(str[i]<str[0]) cp -= (N-x-i);
		if(cp<0 || M<0) continue;
		// N-LこからM個選んでcp個
		ZERO(dp);
		dp[0][M][cp]=1;
		
		FOR(y,N) {
			FOR(i,M+1) FOR(j,cp+1) {
				if((y<x || y>=x+L) && i>0 && j>=N-y)
					dp[y+1][i-1][j-(N-y)]=(dp[y+1][i-1][j-(N-y)]+dp[y][i][j])%1000000007;
				dp[y+1][i][j]=(dp[y+1][i][j]+dp[y][i][j])%1000000007;
			}
		}
		p += dp[N][0][0];
	}
	
	// M個の並べ方
	FOR(i,M) {
		p=(p*(i+1))%1000000007;
	}
	
	//str[0]より大きい文字の並べ方
	x=(N-1)-(str[0]-'a');
	FOR(i,L) if(str[i]>str[0]) x--;
	FOR(i,x) {
		p=(p*(i+1))%1000000007;
	}
	
	_P("%lld\n",p);
	return;
}

まとめ

こうDP組めばいいのか…
まだまだDPを組む力が弱いなぁ。