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