TopCoder SRM 567 Div2 Hard MountainsEasy

続いてDiv2 Hard。
http://community.topcoder.com/stat?c=problem_statement&pm=12380

絵を描く際、山の頂上の座標を選ぶと、その下に三角形状に色が塗られる。
N回頂上の座標を選んだ場合、最終的な絵柄が指定された絵柄と一致するような選び方を求める。

まず、必ず選ばなければいけない頂上の座標を求める。
上から見ていって、色が塗られている場所があればそこは選ばなければいけない場所である。
選ばなければいけない場所があったら、そこを選んだことで塗られる場所は選ぶ必要がないので候補から外す。
この処理を上から行うと、選ばなければいけない場所の数Fと選ばなくてもいい場所の数Eがわかる。

後は組み合わせ問題で、N回中、F箇所は１回以上、E箇所は0回以上選ぶ選び方を答える。
自分はだいぶ回りくどいことをしてしまった。
F箇所のそれぞれにおいて、1～N-F回選び、残りのF-1回の組み合わせを再帰的に求め、F=0になったら、今度はN回からE箇所を0～N回選び、残りのE-1回の組み合わせを再帰的に求める、とした。

下手するとE=2450になるのでスタックや実行時間溢れるかと思ったけど、N<=50なので問題なかった。

ll MO=1000000009;
ll tmemo[51][51];
ll pmemo[2501][51];
ll C[2501][51];

class MountainsEasy {
	int MN;
	int TP;
	int W,H;
	char str[51][51];
	public:
	
	ll calc2(int LP,int LN) {
		int i;
		ll& res = pmemo[LP][LN];
		if(res != -1) return res;
		if(LP==0 && LN>0) {
			res=0;
		}
		else if(LN==0) {
			res=1;
		}
		else {
			res = 0;
			for(i=0;i<=LN;i++) {
				ll co = C[LN][i];
				res = (res + co*calc2(LP-1,LN-i)) % MO;
			}
		}
		return res;
	} 
	
	ll calc(int LT, int LN) {
		int i;
		ll& res = tmemo[LT][LN];
		if(res != -1) return res;
		if(LT>LN) return 0;
		
		if(LT==0) {
			res = calc2(MN,LN);
		}
		else {
			res = 0;
			for(i=1;i<=LN-(LT-1);i++) {
				res = (res + C[LN][i]*calc(LT-1,LN-i)) % MO;
			}
		}
		return res;
	}
	
	int countPlacements(vector <string> picture, int N) {
		int x,y,ty,tx;
		H=picture.size();
		W=picture[0].size();
		
		TP=MN=0;
		FOR(y,H) strcpy(str[y],picture[y].c_str());
		FOR(y,H) FOR(x,W) if(str[y][x]=='X') MN++;
		FOR(y,H) FOR(x,W) {
			if(str[y][x]!='X') continue;
			TP++;
			for(ty=y;ty<H;ty++) {
				for(tx=x-abs(ty-y);tx<=x+abs(ty-y);tx++) {
					if(tx>=0 && tx<W) str[ty][tx]='.';
				}
			}
		}
		
		ZERO(C);
		for(x=0;x<2501;x++) C[x][0]=1;
		for(x=1;x<2501;x++) for(y=1;y<51;y++) C[x][y]=(C[x-1][y]+C[x-1][y-1])%MO;
		FOR(x,51) FOR(y,51) tmemo[x][y]=-1;
		FOR(x,2501) FOR(y,51) pmemo[x][y]=-1;
		
		MN-=TP;
		return calc(TP,N); 
	}

};

さて、Editorialみたらもっと賢い手法で組み合わせを求めていた。
N個からFの要素を１回以上、Eの要素を０回以上選ぶ関数をC(N,F,E)として、１番目の要素から順に決めていく。
その際、Eから選ぶ場合とFから選ぶ場合を計算するが、Fから計算する場合はその要素はもう選ばなくて良いのでF * C(N-1,F-1,E+1)と選ばなくて良い要素が1増えると考えている。

こちらの方がコードが単純だし計算量もO(NF)程度と少ない(自分の方法はO(NE)=O(NF^2))のでいいな。
この組み合わせ計算はほかでも使えそうなので覚えておこう。

まとめ

組み合わせ計算に苦戦したものの、一応自分で解き切れたのはよかった。