mayoko’s diary

プロコンとかいろいろ。

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;
    }
};