CODE FESTIVAL 2017 Qual B : E - Popping Balls

本番中解けて良かった。
http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_e

問題

赤いボールがA個、青いボールがB個が順に並んでいる。
以下の手順でボールを列から抜き出していく。

• 最初に２値s,tを定める
• ボールの列のうち、先頭から1,s,t番目のいずれかを選択し抜き出す

ボールの抜出順は何通りあるか。

解法

AとBのどちらかが0の場合1通りなのは明らか。
よって、1＜s＜t、かつAもBも正の場合を考える。

s,tをどのように決めるかを考えよう。
まず最初に赤を取っていく間は1番目を抜き出せばいいのでs,tの値は関係ない。
途中赤がa個、青がb個の段階で初めて青を抜き出すとする。
この時、t=(a+1)とするのが良い。そうすると以後ボールがa個になるまで、１個目かt個目を選べば(ボールが残っている限り)赤青好きな方を選べる。
あえてそれより大きなtを取る理由はない(青を選べるタイミングが減ってしまうため)

残りa個になった段階で赤がp個、青がq個になったとする。
その後は、また赤がとりたければ1番目を抜き出せばよい。
さらに赤がp'個になった段階で初めて青を選ぶ場合、今度はs=p'+1とするとまたその後残りp'個になるまでは赤青選ぶことができる。
残りp'個になると、以後は1番目を抜き出すしかないので一意に決まる。

こんな感じで、s,tを定めないと青色が抜き出せないタイミングでs,tを定め、その前後の組み合わせをメモ化再帰などで求めていけばよい。

ll mo=1000000007;
int A,B;
ll memo[2020][2020];
ll C[2040][2040];
ll CS[2040][2040];


ll dfs(int A,int B) {
	if(A==0 || B==0) return 1;
	if(memo[A][B]>=0) return memo[A][B];
	// take A;
	ll ret=dfs(A-1,B);
	// take B;
	int a=A,b=B-1;
	// take until a+b==A;
	ret += CS[b][min(a,b)+1]-CS[b][0]+mo;
	return memo[A][B]=ret%mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(memo);
	cin>>A>>B;
	if(A==0 || B==0) {
		cout<<1<<endl;
		return;
	}
	for(i=0;i<=2020;i++) {
		C[i][0]=C[i][i]=1;
		if(i) for(j=1;j<i;j++) (C[i][j]=C[i-1][j-1]+C[i-1][j])%=mo;
		FOR(j,2020) (CS[i][j+1]=CS[i][j]+C[i][j])%=mo;
	}
	
	ll ret=0;
	B--;
	for(int a=0;a<=A;a++) {
		for(i=0;i<=a;i++) if(a-i<=B) {
			(ret += C[B][a-i]*dfs(i,a-i))%=mo;
		}
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

1600ptがまっとうに解けたのは初めてか？