WARush

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

SRM609 Div2 Hard "VocaloidsAndSongs"

問題

TopCoder Statistics - Problem Statement

ボーカロイドのグミ・イア・マユは歌うことが大好きだ。彼女らはS曲入っているアルバムをリリースすることにした。S個のそれぞれの曲は3人の内、少なくとも1人は担当する必要がある。それさえ守れば、1つの曲を2人、または3人同時に歌ってもよい。グミ・イア・マユの歌った曲の数はそれぞれ、gumi, ia, mayuである。

担当するボーカロイドの組み合わせが異なれば、それらは異なるアルバムである、としたときに、アルバムの作り方の数を返せ。

制約

1 <= S <= 50
1 <= gumi, ia, mayu <= S


考えたこと

グミしか知らない・・・

典型的なdp問題。もしくはメモ化再帰。何も考えずにコーディング!

dp[song][gumi][ia][mayu] := song個の曲をそれぞれのボーカロイドがgumi, ia, mayu だけ歌ったときの作り方の数

dp[0][0][0][0] = 1;
dp[S][G][I][E](S = G + I + E)の総和が答え


ソースコード

int N;
int MOD = 1000000007;
long long memo[55][55][55][55];

class VocaloidsAndSongs {

    public:



    long long dfs(int id, int rg, int ri, int rm){
        
        if (id == N) {
            if (rg == 0 && ri == 0 && rm == 0) {
                return 1;
            } else {
                return 0;
            }
        }

        if (memo[id][rg][ri][rm] != -1) return memo[id][rg][ri][rm];

        long long res = 0;

        // rem...
        if (rg == 0 && ri == 0 && rm == 0) {
            return 0;
        }

        // g
        if (rg > 0) {
            res += dfs(id + 1, rg - 1, ri, rm);
            res %= MOD;
        }

        // i
        if (ri > 0) {
            res += dfs(id + 1, rg, ri - 1, rm);
            res %= MOD;
        }

        // m
        if (rm > 0) {
            res += dfs(id + 1, rg, ri, rm - 1);
            res %= MOD;
        }

        // g i
        if (rg > 0 && ri > 0) {
            res += dfs(id + 1, rg - 1, ri - 1, rm);
            res %= MOD;
        }

        // g m
        if (rg > 0 && rm > 0) {
            res += dfs(id + 1, rg - 1, ri, rm - 1);
            res %= MOD;
        }

        // i m
        if (ri > 0 && rm > 0) {
            res += dfs(id + 1, rg, ri - 1, rm - 1);
            res %= MOD;
        }

        // g i m
        if (rg > 0 && ri > 0 && rm > 0) {
            res += dfs(id + 1, rg - 1, ri - 1, rm - 1);
            res %= MOD;
        }

        return memo[id][rg][ri][rm] = res;
    }

    int count(int S, int gumi, int ia, int mayu) {
        N = S;

        memset(memo, -1, sizeof(memo));

        return dfs(0, gumi, ia, mayu);
    }
};