TopCoder SRM 828 : Div1 Easy Div2 Hard ImproveName

GCRと重なったせいで参加者が非常に少なかった回。
https://community.topcoder.com/stat?c=problem_statement&pm=17559&rd=19192

問題

N文字の文字列Sと、整数Kが与えられる。
SのうちK要素を選び、並べ替えることでSより辞書順で小さい文字列を作りたい。
K要素の選び方は何通りか。

解法

選んだK要素が、単調増加でないようにすればよい。
そこで
dp(n, k, b, max) := Sのprefix n文字のうちk文字選んだ時、選んだ文字の並びが単調増加かどうかが真偽値bで、最大値がmaxであるような選び方の数
をO(N^2*c) (cは文字の種類)で求めて行けばよい。
dp(N,K,true,*)の総和が解となる。

ll mo=1000000007;
ll dp[2][26][3030];

class ImproveName {
	public:
	int improve(string name, int K) {
		int N=name.size();
		
		ZERO(dp);
		dp[0][0][0]=1;
		
		int i,j,x,y;
		FOR(i,N) {
			name[i]-='A';
			for(j=N-1;j>=0;j--) FOR(x,2) FOR(y,26) if(dp[x][y][j]) {
				if(name[i]<y) (dp[1][y][j+1]+=dp[x][y][j])%=mo;
				else (dp[x][max(y,(int)name[i])][j+1]+=dp[x][y][j])%=mo;
			}
		}
		
		ll ret=0;
		FOR(x,26) ret+=dp[1][x][K];
		return ret%mo;
	}
}

まとめ

まぁMediumを1発で通せなかったので、出てたらレート落ちてたっぽいけども…。