SRM 673 Div1 Easy - BearCavalry
問題
TopCoder Statistics - Problem Statement
問題概要
人の戦士と体の馬がいる。それぞれに対しての番号をふる。番目の戦士、馬の強さをそれぞれ、と表す。そして、戦士1人と馬1体でユニットを組み、合計個のユニットを組むことを考える。このとき、ユニットの強さは、戦士の強さと馬の強さの積で与えられる。
番の番号を与えられた戦士はbraveheart
と言われ、他のどの戦士よりも強いユニットを結成しなければならない。人の戦士と体の馬の強さが与えられる時、ユニットの組み方が何通りあるかを求め、で割った余りを答えよ。
アイデア
まず、braveheart
がどの馬とユニットを組むかを固定する。番目の馬とユニットを組むとすると、braveheart
の強さはとなる。残った人の戦士と体の馬で個のユニットを組み、どのユニットもこの値以上にならないような組合せを求め、最後に足し合わせることで答えが求まる。
では、そのようなユニットの組み方が何通りあるか考える。番目の戦士に対して、braveheart
未満の強さになる馬が何体いるかは体の馬の強さを走査していけば数え上げることが出来る。そうすれば、弱い馬ほど組める戦士が多く、強い馬ほど組める戦士がすくないのは明らかである。ここで、最も強い馬から順に組む戦士を決めていくことにすると、その馬と組める人数をどんどん掛けあわせていけば良い。そして強い馬順に辿って行く時に、累積和的に次に人数を持ち越していくことで組合せの数を実現できる。
例えば、で考えると、braveheart
とユニットを組む馬を固定したら、残りの人の戦士と体の馬で個のユニットで組む。その際に人の戦士が組むことの出来る馬の数がだとすると、最も強い馬と組むことの戦士は人で、次の馬は残った人のうちどちらでもよく、残りが最後と組むという形になる。なので、この時の組み合わせは 通りとなる。このような動作をループの後半部で実現している。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(i=0;i<n;++i) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define mp make_pair #define pb push_back #define fi first #define sc second const long mod=1e9+7; class BearCavalry { public: int countAssignments(vector<int> warriors, vector<int> horses) { int i,j; int n=horses.size(); long ret=0; rep(i,n){//braveheartの乗る馬を決定 //braveheartの強さ(これ以上になってはいけない) int BHst=warriors[0]*horses[i]; vector<int> h(horses); //braveheartの乗る馬を除いておく h.erase(h.begin()+i); sort(h.begin(),h.end()); //j番目の馬まで選んでもbraveheartより強くならない int ct[50]={0}; //j番目のwarriorはどこまで選んでよいか for(j=1; j<n; ++j){ int k=0; while(k<h.size() && warriors[j]*h[k]<BHst) ++k; ++ct[k]; } //どの馬も選べない戦士がいるときは不可 if(ct[0]>0) continue; long tmp=1; for(j=n-1; j>0; --j){ //選べる馬がない if(ct[j]==0){ tmp=0; break; } else{ tmp*=ct[j]; ct[j-1]+=ct[j]-1; } tmp%=mod; } ret+=tmp; ret%=mod; } return (int)ret % (int)mod; } };