kmjp's blog

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

TopCoder SRM 541 Div1 Medium AkariDaisukiDiv1

最近TCOGCJだでSRMのMediumつぶしがおろそかだったので。
http://community.topcoder.com/stat?c=problem_statement&pm=11888

問題

文字列W,A,Dが与えられる。
文字列xに対し、f(x)= W+x+A+x+D で定義できる。

ここでさらに文字列S,Fと整数kが与えられる。
f^k(S)中、部分文字列としてFは何回登場するか答えよ。

解法

まず、f(x)の長さがF以上になるまでは適当に何回か関数fを適用しておくと後の処理が楽である。
以下のコードでは、100文字を超えるまではfを繰り返した。

f^i(x)について、Fの登場回数及び先頭100文字(prefix)と末尾100文字(postfix)を覚えておき、DPしていく。
この時、f^(i+1)(x)におけるFの登場回数は、f^i(x)における登場回数の2倍に、W+prefix、postfix+A+prefix、prefix+Dの各文字列に登場するFの回数を加えたものである。

よって順々にiを増やしながらf^i(x)におけるFの回数を数えることができる。
ただ、この問題はkの上限が10^7とかなり大きいため、文字列検索をしながらiをインクリメントするとTLEする。

一方、iが100を超えるとprefixはWを繰り返したもの、postfixはDを繰り返したものになるので、W+prefix、postfix+A+prefix、prefix+DにおけるFの登場回数は常に同じになる。
この登場回数をaddとすると、f^(i+1)(x)のFの登場回数はf^i(x)*2+addと簡単な式で書けるようになり、10^7回繰り返してもTLEしなくなる。

ll mo=1000000007;

class AkariDaisukiDiv1 {
	public:
	int dp[2][51];
	int countF(string W, string A, string D, string S, string F, int k) {
		int i,j;
		ll ret=0,add;
		
		while(S.size()<=100 && k) S=W+S+A+S+D, k--;
		FOR(i,(int)S.size()-(int)F.size()+1) ret+=S.substr(i,F.size())==F;
		if(k<=0) return (int) ret;
		string s1=S,s2=S;
		
		FOR(i,F.size()+5) {
			if(k--<=0) return (int) ret;
			s1=s1.substr(0,100);
			s2=s2.substr(s2.size()-100);
			
			add=0;
			
			string ss=s2+A+s1;
			s1=W+s1;
			s2=s2+D;
			FOR(j,W.size()) add+=F==s1.substr(j,F.size());
			for(j=100-F.size()+1;j<100+A.size();j++) add+=F==ss.substr(j,F.size());
			FOR(j,D.size()) add+=F==s2.substr(s2.size()-F.size()-j,F.size());
			s1=s1.substr(0,100);
			s2=s2.substr(s2.size()-100);
			
			ret = (ret*2+add) % mo;
		}
		
		while(k-->0) ret=(ret*2+add) % mo;
		return (int)ret;
		
	}
}

まとめ

結局f^i(x)の先頭と末尾はある程度以降は同じになる点がポイント。
これはすんなり自力で解けた。