Codeforces#247に参加。
ABCDがかなりのペースで解けて好調。Eは凡ミスで落としたが、そこそこの順位。
http://codeforces.com/contest/431/problem/C
問題
以下のような根付き木を考える。
- 完全なK分木であり、各頂点はK個の子を持つ。
- 各頂点が持つK個の子への辺のコストは1,2,3,...,Kである。
根からの最短到達コストがちょうどNで、かつコストD以上の辺を1回以上通過しないとたどり着けない頂点の数を答えよ。
解法
単純な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な気がするな…。