Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-11-19SRM488 Div1

日本人がたくさんいる部屋でした

250WAで0点でした。だめだ・・・

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