Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-11-15SRM523 Div1(Practice)

SRM523 Div1 500 BricksN

| 02:29 | SRM523 Div1 500 BricksN - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM523 Div1 500 BricksN - SRM diary(Sigmar) SRM523 Div1 500 BricksN - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

1つの列について並べ方を列挙していって、再帰的に上に登っていく感じ

連続する空白+連続するブリックで適当に再帰的に並べ方を数えると50^4くらいの計算量になる

もう少し場合分けして工夫すると50^3に落とせるが別にそこまでする必要はない


ソースコード

const int MOD=1000000007;
int memo[52][52];
int memo2[52];

class BricksN {
public:
	int k;

	int countPat(int w) {//幅wの連続するブリックの置き方の場合の数
		if(w==1) return 1;
		if(memo2[w]>=0) return memo2[w];

		int res=0;
		if(k>=w) res++;//幅wのブリックを1つだけ置く場合は再帰すると無限ループになるので別扱いする
		for(int i=1; i<=min(w-1, k); i++) {//次に置くブリックの幅をiとして再帰する
			res=((ll)res+countPat(w-i))%MOD;
		}

		memo2[w]=res;
		return res;
	}

	int rec(int w, int h) {
		if(h==0 || w<=1) return 1;
		if(memo[w][h]>=0) return memo[w][h];

		int res=1;//ブリックを1つも置かない場合のみ別扱いで+1しておく
		//連続する空白→連続するブリックの順に並べる
		for(int i=1; i<=w-1; i++) {//次に連続する空白の数をiとする
			for(int j=1; i+j<=w; j++) {//空白の右側に連続するブリックの数をjとする
				//rec(j+1, h-1)で連続するブリックの上に置く場合の数を算出
				//rec(w-(i+j),h)で連続するブリックの右側に置く場合の数を算出
				res=((ll)res+(ll)countPat(j)*rec(j+1, h-1)%MOD*rec(w-(i+j), h)%MOD)%MOD;
			}
		}

		memo[w][h]=res;
		return res;
	}

	int countStructures(int w, int h, int _k) {
		int res;

		k=_k;
		memset(memo, -1, sizeof(memo));
		memset(memo2, -1, sizeof(memo2));

		//関数recが左端に1つ以上空白を確保するようになっているため、幅を1つ増やして引数とする
		res=rec(w+1, h);
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111115