TopCoder SRM584 Div1 Med 600 Excavations
問題文概要
いくつかの構造物が埋まっている.
$ i $ 番目の構造物は, $ \mathit{kind}_i $ という種類のもので, 位置 $ i $ の深さ $ \mathit{depth}_i $ に埋まっている.
いくつかの場所を, 最大 $ D $ 掘れる機械で掘る. (この $ D $ は与えられない)
すると, 見つかったのは $ K $ 個の構造物で, 種類の集合(i.e. 重複を排除したもの)は $ \mathit{found} $ であった.
掘った場所の組合せとしてありうるものの個数を答えよ.
制約
$ 1 \le n \le 50,\ 1 \le \mathit{depth}_i \le 10^5 $.
解法
とりあえず, 掘る深さ $ D $ を固定し, その深さの構造物を少なくとも一つ掘り出すとする.
"found に含まれるやつのうち, 深さ $ D $ 以下のやつらを, 全ての種類が出るように, かつその深さのを一つ以上含むように $ i $ 個掘り出すやり方" は, DP をすれば求まる.
"その深さ $ D $ より大のやつらを, $ i $ 個掘り出すが, そのうち一番浅い所に, found に含まれないものがあるやり方" も, DP をすれば求まる.
あとは掛けて足せばよい.
"そのうち一番浅い所に, found に含まれないものがある" を忘れて 1WA.
"今見てる kind, いまいくつ掘ったか, max 掘り出した深さ, min 掘り出せなかった深さ" を持ってメモ化再帰するのが楽っぽい.
ソースコード
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// 187.12 pts
long long Excavations::count( vector <int> kind, vector <int> depth, vector <int> found_, int K ){
vector<vector<long long>> C(200, vector<long long>(200));
rep(i, 200){
C[i][0] = C[i][i] = 1;
for(int j = 1; j < i; ++j) C[i][j] = C[i-1][j-1] + C[i-1][j];
}
const int n = size(kind);
const int t = 55;
vector<int> found(t);
for(auto f : found_) found[f] = true;
vector<int> ds;
rep(i, n) if(found[kind[i]]) ds.emplace_back(depth[i]);
sort(all(ds));
ds.erase(unique(all(ds)), end(ds));
long long res = 0;
for(auto d : ds){
// この深さ掘る. この深さのを少なくとも一つ使う.
unordered_map<int, int> use, use_d;
vector<pair<int, int>> not_use;
rep(i, n){
if(found[kind[i]]) if(depth[i] <= d) ++use[kind[i]];
if(found[kind[i]]) if(depth[i] == d) ++use_d[kind[i]];
if(depth[i] > d) not_use.emplace_back(depth[i], found[kind[i]]);
}
sort(all(not_use));
if(use.size() != found_.size()) continue;
// それぞれの kind を少なくとも一つ使い, 少なくとも一つ d のを使う
vector<long long> res_1;
{//{{{
array<vector<long long>, 2> dp;
dp[0] = dp[1] = vector<long long>(K+1, 0);
dp[0][0] = 1;
for(auto kv : use){//{{{
const int k = get<0>(kv);
array<vector<long long>, 2> qb;
qb[0] = qb[1] = vector<long long>(K+1, 0);
const int A = use_d[k], B = use[k] - use_d[k];
rep(i, A+1) rep(j, B+1) if(i+j > 0){
rep(now, K+1) if(now+i+j <= K){
if(i == 0) qb[0][now+i+j] += dp[0][now] * C[A][i] * C[B][j];
else qb[1][now+i+j] += dp[0][now] * C[A][i] * C[B][j];
qb[1][now+i+j] += dp[1][now] * C[A][i] * C[B][j];
}
}
swap(dp, qb);
}//}}}
res_1 = dp[1];
}//}}}
// d よりでかいのを, "一番最初は found でないの" という条件付きで使う.
vector<long long> res_2;
{//{{{
tr << not_use << endl;
array<vector<long long>, 2> dp;
dp[0] = dp[1] = vector<long long>(K+1, 0);
dp[0][0] = 1;
for(auto df : not_use){
array<vector<long long>, 2> qb = dp;
rep(now, K){
if(get<1>(df)){
qb[1][now+1] += dp[1][now];
}else{
qb[1][now+1] += dp[0][now];
qb[1][now+1] += dp[1][now];
}
}
swap(dp, qb);
}
res_2 = dp[1];
res_2[0] = 1; // 何も使わないのは O.K.
}//}}}
rep(k, K+1) res += res_1[k] * res_2[K-k];
}
return res;
}