kmjp's blog

競技プログラミング参加記です

Good Bye 2015 : D. New Year and Ancient Prophecy

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した。