裏紙

ほぼ競プロ、たまに日記

SRM 673 Div1 Easy - BearCavalry

問題

TopCoder Statistics - Problem Statement

問題概要

n人の戦士とn体の馬がいる。それぞれに対して0 \verb|~| n-1の番号をふる。i番目の戦士、馬の強さをそれぞれw_ih_iと表す。そして、戦士1人と馬1体でユニットを組み、合計n個のユニットを組むことを考える。このとき、ユニットの強さは、戦士の強さと馬の強さの積で与えられる。

0番の番号を与えられた戦士はbraveheartと言われ、他のどの戦士よりも強いユニットを結成しなければならない。n人の戦士とn体の馬の強さが与えられる時、ユニットの組み方が何通りあるかを求め、10^9 + 7で割った余りを答えよ。

  •  2 \leq n \leq 50
  •  1 \leq w_i , h_i \leq 1000

イデア

まず、braveheartがどの馬とユニットを組むかを固定する。i番目の馬とユニットを組むとすると、braveheartの強さは w_0*h_iとなる。残ったn-1人の戦士とn-1体の馬でn-1個のユニットを組み、どのユニットもこの値以上にならないような組合せを求め、最後に足し合わせることで答えが求まる。

では、そのようなユニットの組み方が何通りあるか考える。j番目の戦士に対して、braveheart未満の強さになる馬が何体いるかはn-1体の馬の強さを走査していけば数え上げることが出来る。そうすれば、弱い馬ほど組める戦士が多く、強い馬ほど組める戦士がすくないのは明らかである。ここで、最も強い馬から順に組む戦士を決めていくことにすると、その馬と組める人数をどんどん掛けあわせていけば良い。そして強い馬順に辿って行く時に、累積和的に次に人数を持ち越していくことで組合せの数を実現できる。

例えば、n=4で考えると、braveheartとユニットを組む馬を固定したら、残りの3人の戦士と3体の馬で3個のユニットで組む。その際に3人の戦士が組むことの出来る馬の数が3,3,2だとすると、最も強い馬と組むことの戦士は2人で、次の馬は残った2人のうちどちらでもよく、残りが最後と組むという形になる。なので、この時の組み合わせは 2*2*1=4通りとなる。このような動作をループの後半部で実現している。

実装(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;
    }
};