Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-11-23SRM488 Div1(復習)

SRM488 Div1 500 TheBoredomStoreDivOne

| 23:06 | SRM488 Div1 500 TheBoredomStoreDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM488 Div1 500 TheBoredomStoreDivOne - SRM diary(Sigmar) SRM488 Div1 500 TheBoredomStoreDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

ir5さんの記事を見て、共通パートと残余パートに分ければ解ける気がしたので解いてみた。

大まかな方針としては、共通パートの探索を先にして記憶しておき、残余パートの探索時に使用可能な共通パートの最長のものを持ってくるという方法。

共通パート1の探索は、Jの中でインデックスk,lの全ての組み合わせに対し、k,lで終わる共通部分文字列の最大長を記憶する。Bは逆にk,lで始まる共通部分文字列の最大長を記憶する。

残余パートはJとBの共通部分文字列s全てに対し、Jはsの前にくっつけられる最長の共通パート1を探索、Bはsの後ろにくっつけられる最長の共通パート2を探索して、両方の共通パート長が0より大きい場合のみ有効な解とする。

計算量はO(n^4)です。

感想としては添え字周りの実装が大変。本番中に思いついても解けなかった可能性大です。。


以下、ソースです。

システムテストは通ります。

class TheBoringStoreDivOne {
public:
	string find(string J, string B) {
		string res;
		int jsz=J.size(), bsz=B.size();

		//Jのインデックスk,lの組に対し、k,lで終わる共通部分文字列の最大長を記憶
		int dpj[52][52];
		memset(dpj, 0, sizeof(dpj));
		for(int a=0; a<jsz; a++) {
			for(int b=a+1; b<jsz; b++) {
				int match=-1;
				for(int i=a, j=b; i<=b && j<=jsz; i++, j++) {
					if(match>=0) {
						if(i==b || j==jsz || J[i]!=J[j]) {
							for(int k=i-1, l=j-1; k>=match; k--, l--) {
								dpj[k][l]=max(dpj[k][l], k-match+1);
								dpj[l][k]=max(dpj[l][k], k-match+1);
							}
							match=-1;
						}
					} else {
						if(i<b && j<jsz && J[i]==J[j]) match=i;
					}
				}
			}
		}

		//Bのインデックスk,lの組に対し、k,lで始まる共通部分文字列の最大長を記憶
		int dpb[52][52];
		memset(dpb, 0, sizeof(dpb));
		for(int a=0; a<bsz; a++) {
			for(int b=a+1; b<bsz; b++) {
				int match=-1;
				for(int i=a, j=b; i<=b && j<=bsz; i++, j++) {
					if(match>=0) {
						if(i==b || j==bsz || B[i]!=B[j]) {
							for(int k=i-1, l=j-1; k>=match; k--, l--) {
								dpb[k][l]=max(dpb[k][l], i-k);
								dpb[l][k]=max(dpb[l][k], i-k);
							}
							match=-1;
						}
					} else {
						if(i<b && j<bsz && B[i]==B[j]) match=i;
					}
				}
			}
		}

		//JとBの共通部分文字列(残余パート)を全て探索
		int maxlen=0;
		for(int i=0; i<bsz-1; i++) {
			for(int j=i; j<=bsz-1; j++) {
				for(int k=1; k<jsz; k++) {
					if(k+(j-i)>jsz) break;
					if(B.substr(i, j-i)==J.substr(k, j-i)) {
						//Jの残余パートの前にくっつける最長の共通パートを探索
						int maxjlen=0;
						for(int l=0; l<jsz; l++) {
							if(l>=k-1 && l<k+(j-i)) continue;
							if(l<k) maxjlen=max(maxjlen, dpj[k-1][l]);
							else maxjlen=max(maxjlen, min(dpj[k-1][l], l-(k+(j-i)-1)));
						}
						//Bの残余パートの後ろにくっつける最長の共通パートを探索
						int maxblen=0;
						for(int l=0; l<bsz; l++) {
							if(l>=i && l<=j) continue;
							if(l>=i) maxblen=max(maxblen, dpb[j][l]);
							else maxblen=max(maxblen, min(dpb[j][l], i-l));
						}
						//共通パートが両方とも長さ0より大きいとき、有効な解とする
						if(maxjlen==0 || maxblen==0) continue;
						int tlen=maxjlen+(j-i)+maxblen;
						string tres=J.substr(k-maxjlen, maxjlen+j-i)+B.substr(j, maxblen);
						if(tlen>maxlen || tlen==maxlen && tres<res) {
							maxlen=tlen;
							res=tres;
						}
					}
				}
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101123

2010-11-19SRM488 Div1

SRM488 Div1 250 TheBoredomDivOne

| 20:22 | SRM488 Div1 250 TheBoredomDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM488 Div1 250 TheBoredomDivOne - SRM diary(Sigmar) SRM488 Div1 250 TheBoredomDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

期待値の問題

とりあえずrecursiveに書けそうなので、書いてみる

期待値をf(n,m)とすると、f(n,m)=a*f(n,m)+bの形になるので、このままだと無限ループする

変形するとf(n,m)=b/(1-a)となるので、プログラムを変形

→できた

→サンプルが全然合わない

→うーん・・・

→・・・

→手計算する

→手計算の結果がサンプルと合わない

→あれ?問題勘違いした?

→よく見直す・・・

→・・・

→分からん

→読み違いは見当たらないけど・・

→・・・

→手計算間違っとる(泣)

→考え方は合ってた

→何が間違ってるのか・・

→・・・

→doubleにキャストしないといけないところが勘違いで抜けてた

→直す

→まだ合わない

→まだ間違ってる

→直す

→まだ間違ってる

→直す

→やっと合った

正しい漸化式は以下の通りになった(C(p,q)はpからq個選ぶコンビネーション)

f(n,m)=(f(n+2,m-2)+1)*C(m,2)/C(n+m,2) + (f(n+1,m-1)+1)*(m*n)/C(n+m,2) + (f(n,m)+1)*C(n,2)/C(n+m,2)

f(n+2,m-2)とf(n+1,m-1)はrecursiveに計算すると定数と扱えるので、f(n,m)=a*f(n,m)+bに変形すると、

a=C(n,2)/C(n+m,2)

b=(f(n+2,m-2)+1)*C(m,2)/C(n+m,2) + (f(n+1,m-1)+1)*(m*n)/C(n+m,2) + C(n,2)/C(n+m,2)

となるので、後はf(n,m)=b/(1-a)に当てはめて解くだけ

一応m==0の場合とm==1の場合は分けて書いておこう

(n==1の場合も厳密には分けなければならないが自分のコンビネーションの計算方法だと分けなくても答えは合う)

→(n,m)=(47,47)の場合をテスト

TLEする

→適当に50*50の配列でメモ化する(←間違い)

→47,47が時間内に終わった(←答えが3とか変なのになってたのだが気づかず・・・)

→やっとできた・・・

提出・・・

132点・・・期待値はもっと勉強しないと駄目だな・・

→500へ

500は色々考えたが分からない。難しい・・・時間切れで終了


チャレンジフェーズ

メモ化してない人は・・・いない

LayCurseさんに撃墜される

→ええー自信満々だったんだけど何でだ

→分からん・・・


後で

メモ化の配列が50*50だと全然足りてなかった

47,47だと最終的には94,0になるので、100*50くらいの配列が必要

むしろ片方が決まればもう片方決まるので、1*50の配列でもいい

自分があほすぎて泣ける・・

手計算もまた間違えてまた一杯時間浪費したし、だめだめだ・・


ソースコード

修正しました。システムテスト通ります。

double memo[100][50];

class TheBoredomDivOne {
public:
	double rec(int n, int m) {
		if(memo[n][m]>=0) return memo[n][m];
		double res=0;
		if(m==0) {memo[n][m]=0; return 0;}
		if(m==1) {memo[n][m]=1./(1.-(double)(n*(n-1)/2)/((n+m)*(n+m-1)/2)); return memo[n][m]; }
		res+=(rec(n+1, m-1)+1)*(double)(n*m)/((n+m)*(n+m-1)/2);
		res+=(rec(n+2, m-2)+1)*(double)(m*(m-1)/2)/((n+m)*(n+m-1)/2);
		res=(res+(double)(n*(n-1)/2)/((n+m)*(n+m-1)/2))/(1.-(double)(n*(n-1)/2)/((n+m)*(n+m-1)/2));
		memo[n][m]=res;
		return res;
	}

	double find(int n, int m) {
		double res;

		for(int i=0; i<100; i++) for(int j=0; j<50; j++) memo[i][j]=-1;
		res=rec(n, m);
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101119