C++の練習を兼ねて, 競プロ典型 90 問 の 問題051 (Typical Shop) を解いてみた.
■感想.
1. 問題051は, 過去問 AtCoder Beginner Contest 184 (Programming Contest)に類似した方針で解けそうと気付けたので, AC版に到達出来たと思う.
2. 半分全列挙の復習が出来たので良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題051 を ご覧下さい.
■C++版プログラム(問題051／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vp = vector<pair<LL, int>>; using vl = vector<LL>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define a first #define b second #define all(x) x.begin(), x.end() LL a[44], gCum[1 << 21][22]; int main(){ // 1. 入力情報. int N, K; LL P; scanf("%d %d %lld", &N, &K, &P); rep(i, N) scanf("%lld", &a[i]); // 2. 事前計算. int lCnt = N / 2, rCnt = N - lCnt; vp v; rep(i, 1 << rCnt){ LL p = 0; rep(j, rCnt) if(i & (1 << j)) p += a[lCnt + j]; v.pb({p, __builtin_popcount(i)}); // {値段の合計, 品物の選択数}. } // 3. sort. sort(all(v)); // 4. 累積和. rep(i, v.size()){ rep(j, 21) gCum[i + 1][j] = gCum[i][j]; gCum[i + 1][v[i].b]++; } // 5. インデックス計算用. vl idxs; for(auto &p : v) idxs.pb(p.a); // 6. 集計. LL ans = 0; rep(i, 1 << lCnt){ // 6-1. 左から l個, 右から r個 を 選択. int l = __builtin_popcount(i); int r = K - l; if(r > rCnt || r < 0) continue; // 6-2. 左から l個選択したときの値段の合計は？ LL p = 0; rep(j, lCnt) if(i & (1 << j)) p += a[j]; // 6-3. 値段の合計が, P円以下になるパターンは？ int at = upper_bound(all(idxs), P - p) - idxs.begin(); // 6-4. 加算. ans += gCum[at][r]; } // 7. 出力. printf("%lld\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
[入力例] 5 2 10 3 8 7 5 11 [出力例] 2 ※AtCoderテストケースより [入力例] 5 1 10 7 7 7 7 7 [出力例] 5 ※AtCoderテストケースより [入力例] 40 20 100 1 3 1 3 4 1 3 5 5 3 3 4 1 5 4 4 3 1 3 4 1 3 2 4 4 1 5 2 5 3 1 3 3 3 5 5 5 2 3 5 [出力例] 137846528820 ※AtCoderテストケースより [入力例] 10 3 2021 995 1053 40 877 790 164 389 480 712 284 [出力例] 83 [入力例] 20 15 20210625 514085 670779 73685 129574 5500 1074316 985537 683553 782370 1027170 337636 679081 543707 137884 676487 178211 503220 945119 1158968 1225005 [出力例] 15504 [入力例] 40 27 202107122100 808410568 331920903 1137252447 336354363 222223395 404816299 669779234 1170174052 505664701 199843683 626347986 548544963 1159677821 1167796776 142512466 561977437 1112050623 845111295 497654528 853809473 599682486 137743944 250218090 316303643 1213853118 712804419 868439455 966116317 1210969425 1028496444 184508051 765107727 731625464 185947863 31165189 426137200 677132796 376072355 603715221 478022957 [出力例] 12033222880 |
■参照サイト
051 – Typical Shop