WARush

SRMの結果とか、解けた問題のコードを書いていきます

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];
    }
};