TopCoderOpen 2018 Round4 Easy SumPyramid

あと一歩だったのになぁ。
http://community.topcoder.com/stat?c=problem_statement&pm=14894

問題

高さLのピラミッド状に並んだ数値を考える。
最下段はL個の整数が並んでいる。

各段の上には、1個少ない整数が並んでおり、各値は下の段の隣接要素同士を足した値が格納されている。
高さLと、最上段の数値Tが与えられる。
最下段にくる非負整数の組み合わせは何通りか。

解法

最下段の端からi番目(0-indexed)の値に対し、comb(L-1,i)倍だけ最上段に加算される。
…ということを考えるとあとは最下段の要素を端から順に合計がTを超えないようDPで数え上げるだけ。

int C[1010][1010];
ll dp[1010][1010];
ll mo=1000000007;

class SumPyramid {
	public:
	int countPyramids(int levels, int top) {
		int i,j;
		
		C[1][1]=1;
		for(i=2;i<=1000;i++) {
			for(j=1;j<=i;j++) C[i][j]=min(1010,C[i-1][j]+C[i-1][j-1]);
		}
		
		ZERO(dp);
		dp[0][top]=1;
		for(i=1;i<=levels;i++) {
			for(int x=top;x>=0;x--) {
				dp[i][x]=dp[i-1][x];
				if(x+C[levels][i]<=top) (dp[i][x]+=dp[i][x+C[levels][i]])%=mo;
			}
		}
		return dp[levels][0];
	}
}

まとめ

EasyとMedium以降の難易度が大きすぎて、オンサイト境界以外はEasy早解きみたいになっちゃったね。