問題
https://community.topcoder.com/stat?c=problem_statement&pm=14081&rd=16616
解き方
w[0]について各組み合わせを決めることで、最大にならければならないスコアが決まる。
あとは残りについて、その数を超えないように全ての組み合わせ数を求める。
ここで各兵士について、乗ることができる馬の数を考える。
この数でソートすることで、i番目の兵士は、「乗ることのできる馬の数-(i-1)」が選ぶことのできる数であり、よって組み合わせていく順番が一意に決まる。
ある値（最大スコア）を固定することで、残りを貪欲法で選ぶことができないか、選ぶことのできる観点（各兵士について乗ることのできる馬の数）がないか考える。
コード
class BearCavalry {
public:
int countAssignments(vector<int> warriors, vector<int> horses) {
long long ret=0;
int n=warriors.size();
int MOD=1000000007;
FORE(i,0,n){
int value=warriors[0]*horses[i];
int cur[n-1];
memset(cur,0,sizeof(cur));
FORE(j,0,n-1)FORE(k,0,n)if(k!=i && warriors[j+1]*horses[k]<value)cur[j]++;
sort(cur,cur+n-1);
long long tmp=1;
FORE(j,0,n-1)tmp=(tmp*max(0,cur[j]-j))%MOD;
ret+=tmp;
}
return ret%MOD;
}
};
public:
int countAssignments(vector<int> warriors, vector<int> horses) {
long long ret=0;
int n=warriors.size();
int MOD=1000000007;
FORE(i,0,n){
int value=warriors[0]*horses[i];
int cur[n-1];
memset(cur,0,sizeof(cur));
FORE(j,0,n-1)FORE(k,0,n)if(k!=i && warriors[j+1]*horses[k]<value)cur[j]++;
sort(cur,cur+n-1);
long long tmp=1;
FORE(j,0,n-1)tmp=(tmp*max(0,cur[j]-j))%MOD;
ret+=tmp;
}
return ret%MOD;
}
};