kmjp's blog

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

TopCoder SRM 692 Div1 Medium LinenCenter、Div2 Hard LinenCenterEasy

SRM

配点の割に正答者すくなめ。
https://community.topcoder.com/stat?c=problem_statement&pm=14273
https://community.topcoder.com/stat?c=problem_statement&pm=14274

問題

アルファベット小文字からなる文字列を考える。
L文字の文字列Sを考える。
文字列xに対する関数c(x)は、x中に互いにオーバーラップしない部分文字列としてSが最大何個あるかを示す。

整数N,Kが与えられる。
文字列長が(L*K)～(L*K+N)の文字列xのうち、c(x)=Kとなるものがいくつあるか。

解法

Div2 HardはKMP法の要領で入力文字に対する状態遷移のグラフを作成し、DPすればよい。
文字数が最大(L*K+N)、状態が(L*K)、文字種A=26とするとP(A*(L*K)*(L*K+N))なのでちょっと重いがどうにか間に合う。

Div1 MediumはN,K,Lが大きいのでそうもいかない。
そこで、まずSをK回繰り返し、S同士の隙間や全体の両端に合計で最大N文字挿入することを考えよう。
同じ構成を多重でカウントしないためには、以下のようにしたい。

  • SとSの間に文字列Tを挟むとする。文字列T+Sにおいて、S全体がマッチするのは末尾のSの部分でしかない。

まずDiv2同様に状態遷移グラフを作り、最大N文字までDPしてそれぞれどの状態に至るものが何通りあるか求めよう。
各状態のうち、上記のように後ろにSを付与したとき最後までSにマッチしないケースのみ、先頭または途中に挟むことができる。

その結果より、先頭及びSとSの間には、何文字の追加文字を挟め、それが何通りあるかを数え上げる。
あとは行列累乗の要領で先頭及びSとSの間にあるK箇所の隙間それぞれに、同様に何文字追加文字を挟めるか数える。
最後に先のDPの結果を使い、末尾にさらに何文字追加できるか、またその組み合わせを求める。
末尾に関しては後ろにSを付与させないので、Sとマッチしない組み合わせはすべて利用できる。

int from[3030];
int to[3030];
int stt[1024][26];
const char base='a';
ll mo=1000000009;

void CreateSTT(string& pat) {
	int x,y,z,l;
	ZERO(stt);
	l=pat.size();
	FOR(x,l) {
		FOR(y,26) {
			if(base+y == pat[x]) stt[x][y]=x+1;
			else {
				string pre=pat.substr(0,x)+(char)(base+y);
				for(z=1;z<=x;z++) if(pre.substr(pre.size()-z) == pat.substr(0,z)) stt[x][y]=z;
			}
		}
	}
	FOR(y,26) stt[l][y]=l;
}

class LinenCenterEasy {
	public:
	int countStrings(string S, int N, int K) {
		int i,j,c,d;
		int L=S.size();
		CreateSTT(S);
		
		ZERO(from);
		from[0]=1;
		ll ret=0;
		if(K==0) ret++;
		for(i=1;i<=L*K+N;i++) {
			ZERO(to);
			
			FOR(j,i) FOR(c,26) (to[(j/L)*L+stt[j%L][c]] += from[j])%=mo;
			
			swap(from,to);
			if(i>=L*K && i<=L*K+N) for(j=L*K;j<L*(K+1);j++) ret+=from[j];
		}
		return ret%mo;
	}
}

ll dp[1010][110];
class LinenCenter {
	public:
	vector<ll> mul(vector<ll> a,vector<ll> b) {
		int N=a.size(),i,j;
		vector<ll> r(N);
		FOR(i,N) for(j=0;i+j<N;j++) (r[i+j]+=a[i]*b[j])%=mo;
		return r;
	}
	
	int countStrings(string S, int N, int K) {
		int L=S.size();
		CreateSTT(S);
		int NG[101]={};
		
		ZERO(dp);
		dp[0][0]=1;
		
		int i,x,c;
		FOR(i,N+1) {
			FOR(x,L+1) {
				FOR(c,26) (dp[i+1][stt[x][c]] += dp[i][x])%=mo;
				if(x<L) (dp[i][101] += dp[i][x])%=mo;
			}
		}
		
		FOR(i,L) {
			x=i;
			FOR(c,L-1) {
				x=stt[x][S[c]-'a'];
				if(x==L) NG[i]=1;
			}
		}
		
		vector<ll> E(N+1),A(N+1);
		E[0]=1;
		FOR(i,N+1) FOR(x,L) if(NG[x]==0) (A[i]+=dp[i][x])%=mo;
		while(K) {
			if(K%2) E=mul(E,A);
			A=mul(A,A);
			K/=2;
		}
		ll ret=0;
		FOR(i,N+1) for(x=0;x+i<=N;x++) (ret += E[i]*dp[x][101])%=mo;
		return ret;
		
	}
}

まとめ

Editorialにないし、あまり解法を巷で見かけないしどうしようかと思ったけど、どうにか解くことができた。