WARush

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

SRM613 Div2 Hard "TaroCards"

問題

TopCoder Statistics - Problem Statement

猫のタローはN枚のカードを持っていた。カードには2つの整数が書かれている。あなたはint[] first, secondが与えられる。first[i], second[i]はi番目のカードに書かれている2つの数字を表してる。

firstは1~Nの順列となっている。secondは1~10のどれかであり、重複している場合がある。

あなたはint Kも与えられる。タローはカードに書かれている数字の種類がKを超えないように、カードのサブセット(0枚・もしくは全て選ぶパターンもOK)を作ろうと思っている。サブセットの作り方の数を返せ。

制約

1 <= N <= 50
1 <= K <= 2 * N


考えたこと

これは典型問題!

とりあえず簡単のためfirstとsecondをbase 0にしておく。(first=0~N-1, second=0~9)

あとは下記のDPで

  • 状態

dp[i][j][k] := サブセットの選び方の数
i...何番目までのカードを使ったか
j...10枚目以降のカードを何枚使ったか
k...0~9の数字を使っているかのbit


ソースコード

long long dp[55][55][1 << 10];

class TaroCards {

    public:

    // bitの1の数を数える
    int cntBit(int bit) {
        int res = 0;
        for (int i = 0; i <= 10; i++) {
            if (((bit >> i) & 1) == 1) res++;
        }
        return res;
    }

    long long getNumber(vector <int> first, vector <int> second, int K) {
        int n = first.size();

        // base 0
        for (int i = 0; i < n; i++) {
            first[i]--;
            second[i]--;
        }
        

        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 1 << 10; k++) {

                    // not use
                    dp[i+1][j][k] += dp[i][j][k];
                    // use
                    int nj = j;
                    int nk = k | (1 << second[i]);
                    if (first[i] >= 10) {
                        nj = j + 1;
                    }else{
                        nk = nk | (1 << first[i]);
                    }
                    
                    dp[i + 1][nj][nk] += dp[i][j][k];                    
                }
            }
        }

        long long res = 0;
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < 1 << 10; k++) {
                if (j + cntBit(k) <= K){
                    res += dp[n][j][k];
                }
            }
        }

        return res;
    }
};