D,Eで非常にグダグダしたが、最終的にACしたので辛うじてレート微増だった。
http://codeforces.com/contest/611/problem/D
問題
N文字の整数列Sが与えられる。
これを幾つかの文字列に分割したとき、前の桁から順に昇順になるようにしたい。
そのような分割方法は何通りあるか。
解法
dp[x][y] := (S[0..y]までを分割したとき、最後の文字列がS[x..y]でありかつ条件を満たす分割数の総和)
とする。dp[*][N-1]の総和が解となる。
S[z..(x-1)]とS[x..y]が同じ桁数になる、すなわちz=x-1-(y-x)とする。
S[z..(x-1)]とS[x..y]を比較して後者が大きいならdp[x][y] := sum_(z≦i<x) dp[z][x-1]、そうでないならdp[x][y] := sum_(z<i<x) dp[z][x-1]となる。
S[z..(x-1)]とS[x..y]の大小比較は、SuffixArrayでも行けるらしいが、自分はLCSの要領で何桁目で大小が確定するかを求めた。
int N; string S; ll mo=1000000007; int len[5050][5050]; int num[5050][5050]; int sum[5050][5050]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>S; for(y=N-1;y>=0;y--) { for(x=y-1;x>=0;x--) { if(S[x]<S[y]) { len[x][y]=1; } else if(S[x]==S[y]) { if(y==N-1) len[x][y]=505050; else len[x][y]=len[x+1][y+1]+1; } else { len[x][y]=505050; } } } FOR(x,N) num[0][x]=1, sum[1][x]=1; for(x=1;x<N;x++) { if(S[x]=='0') { for(y=x;y<N;y++) sum[x+1][y]=sum[x][y]; } else { for(y=x;y<N;y++) { l=y-x+1; int px=x-l; if(px>=0 && len[px][x]>l) px++; px=max(px,0); num[x][y] = sum[x][x-1]-sum[px][x-1]; if(num[x][y]<0) num[x][y]+=mo; sum[x+1][y]=sum[x][y]+num[x][y]; if(sum[x+1][y]>=mo) sum[x+1][y]-=mo; } } } ll ret=0; FOR(x,N) ret+=num[x][N-1]; cout<<ret%mo<<endl; }
まとめ
地味にメモリ制限が厳しくて、最初MLEした。