SRM584 Div2 Hard "Excavations2"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12644
訳
昔々、ルリタニアと呼ばれる文明があった。0からn-1と番号つけられた建物が建っていた。図書館・商店・神殿といった、様々なものがあった。その種類には1から50の整数がつけられていた。i番目の建物の種類はkind[i]である。
千年の経過とともにルリタニアは衰退し、建物は砂に埋もれ、隠れてしまった。現在、ある勇敢な考古学者がK個の建物を発見した。
あなたはint kind, foundそしてint Kが与えられる。発掘によって発見された建物の種類はint foundによって説明される。ある種類の建物が、複数個見つかっていても、foundにはその種類の番号が1つしか入っていない(つまりはstlのsetみたいなもの)
与えられた情報から、建物の見つけ方のK-タプルの数を返せ。
制約
1 <= kind, foundの要素数 <= 50
考えた事
見つけた建物の種類単位でDPする。
dp[i][j] := found[i]番目までで、j個建物を見つけたときのパターン数
foundの0番目(0-base)を考えるときに、0個建物を見つけるパターンは1個ある(まだfoundを1つも処理していないので)。なのでdp[ 0 ][ 0 ] = 1とする。更新はfound[ i ]の数をn、見つけた建物の数をkとすると、その種類での見つけ方はn_C_kだけあるので、dp[ i+1 ][ j+k ] = dp[ i ][ j ] * n_C_kとする。
ソースコード
long long C[55][55]; long long dp[55][55]; class Excavations2 { public: long long count(vector <int> kind, vector <int> found, int K){ // C初期化 memset( C, 0, sizeof(C) ); for( int i = 0; i <= 50; i++ ){ C[i][0] = 1; } for( int i = 1; i <= 50; i++ ){ for( int j = 1; j <= i; j++ ){ C[i][j] = C[i-1][j-1] + C[i-1][j]; } } // 種類ごとの建物の数を出す int cnt[55] = { 0 }; for( int i = 0; i < kind.size(); i++ ){ cnt[kind[i]]++; } // dp初期化 memset( dp, 0, sizeof(dp) ); dp[0][0] = 1; // dp更新 int n = found.size(); for( int i = 0; i < n; i++ ){ for( int j = 0; j < K; j++ ){ for( int k = 1; k <= K - j; k++ ){ int n = cnt[found[i]]; // found[i]の建物の数 dp[i+1][j+k] += dp[i][j] * C[n][k]; } } } return dp[n][K]; } };