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