SRM 673 div1 easy: BearCavalry
体調悪かったので SRM 673 は不参加です。
解法
流れとしては, warrior[0] が何番目の horse を使うかで場合分けをして, それらの場合の足し算をする, という方針でやります。
ということで, 1 番目以降の warrior さんが warrior[0] * horse[i] の値未満に i 以外の馬を使ってなる方法を求めます。
warrior の強さを高い順に, horse の強さを低い順にソートすると, i < j を満たす整数の組について, warrior[i] がある馬を使えるならば, warrior[j] もその馬を使える, という関係が成り立ちます。なので, warrior の強い順にソートすれば, その人が使える馬の数を数えて, それより前に馬を選んだ人数分その数から引いた数だけ, 馬を選ぶ方法があります。この値を掛け算していけば良いです。
const int MAXN = 55; const ll MOD = 1e9+7; ll calc(int maxi, int remove, vector<int> w, vector<int> horse) { int n = horse.size(); vector<int> h(n-1); { int k = 0; for (int i = 0; i < n; i++) { if (i == remove) continue; h[k++] = horse[i]; } } n--; ll ret = 1; for (int i = 0; i < n; i++) { int j = 0; for (j = 0; j < n; j++) { if (w[i]*h[j] >= maxi) break; } int cnt = j-i; if (cnt <= 0) return 0; (ret *= cnt) %= MOD; } return ret; } class BearCavalry { public: int countAssignments(vector <int> warriors, vector <int> horses) { int n = warriors.size(); vector<int> w(n-1); for (int i = 1; i < n; i++) w[i-1] = warriors[i]; ll ret = 0; sort(w.begin(), w.end()); reverse(w.begin(), w.end()); sort(horses.begin(), horses.end()); for (int i = 0; i < n; i++) { int maxi = warriors[0] * horses[i]; ret += calc(maxi, i, w, horses); ret %= MOD; } return ret; } };