WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM673 Div1 Easy " BearCavalry"

解法

とりあえず、一番目の戦士がそれぞれの馬を使った時を試してみる。

残った戦士を降順に、残った馬を昇順にソートしておく。
あとはSample0のもので説明していく

戦士0(5)は馬1(40)を使うぜ!つまり戦闘力は200だぜ!

残った戦士と馬はこんな感じだ!
戦士 8  8  4    ←降順にソート
馬   19 20 25   ←昇順にソート

ここで、戦士0(8)は馬0~1まで使えるぜ!
つまり、パターンは2だぜ!

戦士1(8)は馬0~1まで使えるぜ!
でももう馬は1つ乗られちゃってるぜ!
だから、パターンは1だぜ!

戦士2(4)は馬0~2まで使えるぜ!
でももう馬は2つ乗られちゃってるぜ!
だから、パターンは1だぜ!

結果、パターンは2 * 1 * 1で2だぜ!

事後

ポインツは150ぐらい。
解くスピードを上げたいなぁ


ソースコード

const int MOD = 1000000007;

class BearCavalry {
    public:
    int countAssignments(vector<int> warriors, vector<int> horses) {
        int n = warriors.size();

        // 最初の戦士を除いたもの
        vector<int> w;
        for (int i = 1; i < n; i++) {
            w.push_back(warriors[i]);
        }

        // 戦士を降順にソート
        sort(w.begin(), w.end(), greater<int>());

        // 馬を昇順にソート
        sort(horses.begin(), horses.end());

        int ans = 0;
        // 0 ~ n - 1までの馬を使用する
        for (int i = 0; i < n; i++) {
            int lim = warriors[0] * horses[i];
            // 使用した馬を除いたもの
            vector<int> h;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                h.push_back(horses[j]);
            }
            ans += solve(w, h, lim);
            if (ans >= MOD) ans -= MOD;
        }
        return ans;
    }

    int solve(vector<int> w, vector<int> h, int lim) {
        // printf("lim...%d\r\n", lim);
        int n = w.size();
        long long cnt = 1;
        for (int wi = 0; wi < n; wi++) {
            int h_max = lim / w[wi] + (lim % w[wi] == 0 ? 0 : 1);
            int hi = 0;
            for (; hi < n; hi++) {
                if (h_max <= h[hi]) break;
            }
            int canUseNum = max(0, hi - wi);
            // printf(" %d(%d) %d %d\r\n", wi, w[wi], hi, canUseNum);
            cnt *= canUseNum;
            cnt %= MOD;
        }
        return cnt;
    }
};