Codeforces #273 Div2 D. Red-Green Towers

これも割とあっさり。
http://codeforces.com/contest/478/problem/D

問題

赤と緑のキューブがあり、その数R,Gが与えられる。
これらを使い出来るだけ段数の多いピラミッドを組みたい。
このピラミッドはi段目にi個のキューブがあり、同じ列の中のキューブは同じ色である。

R+G個のキューブでできる最大段数のピラミッドにおいて、色の組み合わせを答えよ。

解法

単純に１段ずつDPしていくだけ。
状態としてRとGの残り数を両方持つと状態数が増えるが、RかGかどちらかだけを持っておけばよい。
i段目までのキューブ数はi*(i+1)/2個の明らかなので、RとGの使用量を覚えておけばもう片方は計算で明らかである。

ll R,G;

ll dp[2000002];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>R>>G;
	ll h=0,t;
	
	dp[0]=1;
	for(h=1;h*(h+1)/2<=R+G;h++) {
		t=h*(h+1)/2;
		for(j=min(t,G);j>=0;j--) if(j+h<=200000) (dp[j+h]+=dp[j])%=mo;
	}
	
	ll tot=0;
	for(x=0;x<=G;x++) if(t-x>=0 && t-x<=R) tot+=dp[x];
	cout << tot%mo << endl;
	
}

まとめ

Div2とはいえDにしては簡単な問題。
正答者も多いしね。