Codeforces #210 Div1. C. Levko and Strings

本番正答者が少なかった難しめのC。
Editorialを見るとコード量は少ないが、これは本番中には思いつかんわ…。
http://codeforces.com/contest/360/problem/C

問題

アルファベット小文字のみで構成されたN文字の文字列Sと、数Kが与えられる。
同様にアルファベット小文字のみで構成されたN文字の文字列Tのうち、T[i..j]>S[i..j]となるような(i,j)の組がK個とれるTの組み合わせ数を答えよ。

解法

もしt[i]>s[i]なら、i<=jS[i..j]となるのでそのような(i,j)の組はN-i個とれる。
もしiの手前m文字についてT[(i-m)..(i-1)]==S[(i-m)..(i-1)]だとするならば、始点をm～(i-1)においてもそれぞれ同様にjを(N-i)個とれるので掛け算してm*(N-i)個の組が取れる。

上記事実をもとに、dp[始点の位置][条件を満たす(i,j)の残りの数]という変数を持って始点と残り組み数でDPする。

• 各始点の位置i・残り組数xにおいて：
  • t[i]S[(i-m)..(i-1)]であってもT[i]を加えることで条件を満たす(i,j)が増えなくなるので、各mについてdp[i+1][x]+=dp[i-m][x]*(S[i]-'a')となる。
    • mを全部ループで回すと遅いので、事前に部分和を取っておく。
  • t[i]>s[i]となるような組み合わせは、T[(i-m)..(i-1)]==S[(i-m)..(i-1)]の時にT[i]を加えることで(1+m)*(N-i)個(i,j)の組みわせが増えるのでdp[i+1][x] += dp[i-m][x-(1+y)(N-i)]*('z'-S[i])となる。

最後にdp[i][K]をi=0～Nで総和を取れば答え。

int N,K;
string S;
ll mo=1000000007;
ll dp[2010][2010],sum[2010][2010];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K>>S;
	dp[0][0]=sum[0][0]=1;
	FOR(i,S.size()) {
		FOR(x,K+1) {
			dp[i+1][x] = sum[i][x]*(S[i]-'a')%mo;
			FOR(y,K+1) {
				j=x-(1+y)*(S.size()-i);
				if(j<0 || i-y<0) break;
				dp[i+1][x] = (dp[i+1][x]+dp[i-y][j]*('z'-S[i]))%mo;
			}
			sum[i+1][x]=(sum[i][x]+dp[i+1][x])%mo;
		}
	}
	y=0;
	FOR(i,S.size()+1) y=(y+dp[i][K])%mo;
	_P("%d\n",y);
	
}

まとめ

答えは短いんだけどなぁ…。