Codeforces #247 Div2 C. k-Tree

Codeforces#247に参加。
ABCDがかなりのペースで解けて好調。Eは凡ミスで落としたが、そこそこの順位。
http://codeforces.com/contest/431/problem/C

問題

以下のような根付き木を考える。

• 完全なK分木であり、各頂点はK個の子を持つ。
• 各頂点が持つK個の子への辺のコストは1,2,3,...,Kである。

根からの最短到達コストがちょうどNで、かつコストD以上の辺を１回以上通過しないとたどり着けない頂点の数を答えよ。

解法

単純なDPで、[根からの深さ][累積コスト][D以上の辺の通過の有無]を状態として数をカウントすればよい。
処理回数はO(N^2*K)なので余裕。

int N,K,D;
ll mo=1000000007;
ll dp[102][101][2];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>K>>D;
	ZERO(dp);
	dp[0][0][0]=1;
	FOR(i,N+1) {
		FOR(j,101) {
			for(x=1;x<=K;x++) {
				if(j+x>N) continue;
				if(x>=D) {
					dp[i+1][j+x][1]+=dp[i][j][0]+dp[i][j][1];
					dp[i+1][j+x][1] %= mo;
				}
				else {
					dp[i+1][j+x][0]+=dp[i][j][0];
					dp[i+1][j+x][0] %= mo;
					dp[i+1][j+x][1]+=dp[i][j][1];
					dp[i+1][j+x][1] %= mo;
				}
			}
		}
	}
	ll ret=0;
	FOR(i,101) ret+=dp[i][N][1];
	cout << ret % mo << endl;
}

まとめ

Div2Cとはいえ、あまりに工夫のないDPな気がするな…。