Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2012-04-25SRM541 Div1

SRM541 Div1 550 AkariDaisukiDiv1

| 01:12 | SRM541 Div1 550 AkariDaisukiDiv1 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM541 Div1 550 AkariDaisukiDiv1 - SRM diary(Sigmar) SRM541 Div1 550 AkariDaisukiDiv1 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

上限が1000万だから単純なループにする問題ですかね

だとすると、Xに対してWaaiとかAkariとかくっつけた時に解が増える増分だけ調べればいいのでは

これって、Xの先頭はWaaiWaaiWaai...になるし、後ろは...DaisukiDaisukiDaisukiになるから、50回以上繰り返せば増分は一定の値に収束するっぽい

Xが短い間は全探索して、ちょっと長くなったらprefixとsuffixだけ覚えて、50回以上になったらあとはループするだけ

やるだけ・・?

なぜ550


書く

増分の計算かなりめんどい

思ったよりは大変だった


できた

提出


ソースコード

const int MOD=1000000007;

class AkariDaisukiDiv1 {
public:
	int countF(string w, string a, string d, string S, string F, int k) {
		int res;

		string x=S;
		string px, sx;
		ll cnt=0;
		int inc=0;
		for(int i=0; i<min(51, k); i++) {
			if(px.empty()) {
				x=w+x+a+x+d;
				if(x.size()>=F.size()) {
					cnt=0;
					for(int j=0; j+F.size()<=x.size(); j++) {
						if(x.substr(j, F.size())==F) cnt++;
					}
				}
				if(x.size()>50) {
					px=x.substr(0, 50);
					sx=x.substr(x.size()-50);
					x.clear();
				}
			} else {
				inc=0;
				string tx=sx+a+px;
				for(int j=sx.size()-F.size()+1; j<=sx.size()+a.size()-1; j++) {
					if(tx.substr(j, F.size())==F) inc++;
				}
				px=w+px;
				sx=sx+d;
				for(int j=0; j<w.size(); j++) {
					if(px.substr(j, F.size())==F) inc++;
				}
				for(int j=sx.size()-d.size()-F.size()+1; j+F.size()<=sx.size(); j++) {
					if(sx.substr(j, F.size())==F) inc++;
				}
				px=px.substr(0, 50);
				sx=sx.substr(sx.size()-50);
				cnt=(cnt*2+inc)%MOD;
			}
		}
		
		for(int i=51; i<k; i++) {
			cnt=(cnt*2+inc)%MOD;
		}
		res=cnt%MOD;
		return res;
	}
};

PraveenPraveen2012/11/14 15:22You've really captured all the esstenials in this subject area, haven't you?

lltwektgdjilltwektgdji2012/11/17 00:38s3e55e <a href="http://weadgecnprbz.com/">weadgecnprbz</a>

zkwvhwizkwvhwi2012/11/17 10:47mzuI7w , [url=http://amjymbwsqtpw.com/]amjymbwsqtpw[/url], [link=http://jtoocgzxmaus.com/]jtoocgzxmaus[/link], http://uoyfejtwsvcz.com/

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120425