SRM584 Div1 Medium "Excavations"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12641
訳
昔々、ルリタニアと呼ばれる文明があった。0からn-1と番号が付けられた、n個の建物が建っていた地点があった。図書館・商店・神殿といった、様々なものがあった。その種類には1から50の整数の番号がつけられていた。i番目の建物の種類はkind[i]である。
千年の時が流れ、ルリタニアは衰退し、建物が建っていた地点は砂に覆われ、建物は隠れてしまっていた。風や地形のため砂の深さは変化していた。i番目の地点は、表面からdepth[ i ]メートル下に埋もれていた。
現在、勇敢な考古学者が、最大Dメートルの深さまで掘れるマシンを使って、K個の場所を掘り出した。すなわち、彼は地上から、最大でもDメートル下の建物しか発見できない。
あなはたint[] kind, depth, found そしてint Kが与えられる。発掘によって発見された建物の種類はfoundにあるものである。ある種類の建物が、複数個見つかっていても、foundにはその種類の番号が1つしか入っていない(つまりはstlのsetみたいなもの)
与えられた情報に合致するような、発掘された地点のK-タプルの数を返せ。そのような地点のセットが1つもないようなら0を返せ。
制約
1 <= kindの要素数 <= 50
1 <= depth[ i ] <= 10^5
解法
こちらを参考しました。m(_ _)m
TopCoder SRM 584 Div1 Medium Excavations - kmjp's blog
参考先に書いてあるとおり、depthは最大10^5とでかいが、kindは最大でも50個しかないので、圧縮しておく。それと、見つからなかった建物を種類で区別するのは無意味なのでまとめて考える。
foundに入っていないもの(not_found)の中で、1つの深さのものに着目する。そこを掘ったとした時に、つまり、Dがその深さ未満であった時、何パターンの掘り方があるか数えていく。
not_foundの数え上げ
例えば、not_foundの重さが以下のようだったとする。
1, 2, 2, 3, 4, 4, 4, 5, 6, 8, 8, 9
ここで、深さ4の場所を少なくとも1つ掘ってみたとする(見つからなかったのだから、Dは4未満となる)。そして、not_found全体でdigだけ掘ったとすると、not_foundでの掘り方は
深さ4までの数_C_dig - 深さ5までの数_C_dig = 8_C_dig - 5_C_dig
となる。深さ5までの数_C_digを引いているのは、深さ4の場所を1つも掘っていない場合の数をひくためである。
foundの数え上げ
not_foundでdigだけ掘ったならば、あとはK - digだけfoundで掘ればよい。それぞれのfoundで、not_foundで掘ってみた場所の深さ未満の場所を、少なくとも1つは掘らなくてはいけない。
例えばfound[i]の深さが以下のようだったとする。
0, 1, 1, 2, 4, 5, 6
さっきnot_foundで4の場所を掘ってみて見つからなかったのだから、Dは4未満となる。つまり、4未満の場所で少なくとも1つは掘らなくてはいけない。found[i]でdigだけ掘る時の掘り方は
found[i]の数_C_dig - found[i]の深さ4以上の数_C_dig = 7_C_dig - 3_C_dig
となる。
事後
Div1 Midにしても難しい・・・
ソースコード
long long C[55][55]; int N; int FN; int F[55][55]; // F[i][j] foundのi番目で、深さj以上のものの int FS[55]; int NF[55]; long long memo[55][55][55]; class Excavations { public: long long dfs( int id, int rem, int limit ){ if( memo[id][rem][limit] != -1 ) return memo[id][rem][limit]; long long res = 0; // 全て見終わった if( id == FN ){ if( rem == 0 ){ res = 1; } }else{ for( int dig = 1; dig <= rem; dig++ ){ res += dfs( id + 1, rem - dig, limit ) * (C[FS[id]][dig] - C[F[id][limit]][dig]); } } return memo[id][rem][limit] = res; } long long count(vector <int> kind, vector <int> depth, vector <int> found, int K){ // C初期化 memset( C, 0, sizeof(C) ); for( int i = 0; i < 55; i++ ){ C[i][0] = 1; } for( int i = 1; i < 55; i++ ){ for( int j = 1; j < 55; j++ ){ C[i][j] = C[i-1][j-1] + C[i-1][j]; } } N = kind.size(); FN = found.size(); // depth圧縮 vector<int> ds; for( int i = 0; i < N; i++ ){ ds.push_back( depth[i] ); } sort( ds.begin(), ds.end() ); ds.erase( unique( ds.begin(), ds.end() ), ds.end() ); for( int i = 0; i < N; i++ ){ depth[i] = find( ds.begin(), ds.end(), depth[i] ) - ds.begin(); } // F, NF初期化 memset( F, 0, sizeof(F) ); memset( FS, 0, sizeof(FS) ); memset( NF, 0, sizeof(NF) ); for( int i = 0; i < N; i++ ){ int id = -1; for( int j = 0; j < FN; j++ ){ if( kind[i] == found[j] ) id = j; } if( id != -1 ){ F[id][depth[i]]++; FS[id]++; }else{ NF[depth[i]]++; } } for( int i = 0; i < FN; i++ ){ for( int j = 50; j > 0; j-- ){ F[i][j-1] = F[i][j] + F[i][j-1]; } } memset( memo, -1, sizeof(memo) ); long long ans = dfs( 0, K, 50 ); int sum = 0; // 見つけられなかった深さで掘ってみる for( int d = 49; d >= 0; d-- ){ int cur = NF[d]; if( cur == 0 ) continue; sum += cur; // 見つけられない建物の総数 // 掘る数 for( int dig = 1; dig <= sum; dig++ ){ // dの部分は最小でも1つは掘るようにする long long not_found_comb = C[sum][dig] - C[sum-cur][dig]; // 見つけたの場合の数を計算する。 long long found_comb = dfs( 0, K - dig, d ); ans += not_found_comb * found_comb; } } return ans; } };