C++の練習を兼ねて, AtCoder Regular Contest 042 の 問題C (おやつ) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を確認の上, 実装したところ, AC版となった.
2. 0-1ナックサック問題 と言われるものとのことで, 新しい知識が増えたので良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 042 解説をご覧下さい.
■C++版プログラム(問題C／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 |
// 解き直し. // https://www.slideshare.net/chokudai/arc042 #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; #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() P p[5050]; int dp[5050]; // 金額i円における満足度の最大値を保存. int main(){ // 1. 入力情報. int N, X, a, b; vector<P> v; scanf("%d %d", &N, &X); rep(i, N){ scanf("%d %d", &a, &b); v.pb({a, b}); } // 2. sort. sort(all(v), greater<P>()); // 3. dp更新. rep(i, N){ repr(j, 5050, 0){ int n = j + v[i].a; if(j <= X && (dp[j] || !j)) dp[n] = max(dp[n], dp[j] + v[i].b); } } // 4. 満足度の最大値は？ int ans = 0; rep(i, 5050) ans = max(ans, dp[i]); // 5. 出力. printf("%d\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 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 |
[入力例] 4 100 30 50 40 40 50 100 60 80 [出力例] 190 ※AtCoderのテストケースより [入力例] 5 100 40 10 30 50 60 80 20 40 20 70 [出力例] 200 ※AtCoderのテストケースより [入力例] 10 654 76 54 62 19 8 5 29 75 28 4 76 16 96 24 79 30 20 64 23 56 [出力例] 347 ※AtCoderのテストケースより [入力例] 25 1234 124 260 184 38 22 80 6 299 51 222 165 73 197 53 44 59 56 317 173 318 75 265 97 98 180 254 9 25 136 197 191 20 217 295 65 45 218 101 173 140 209 147 214 179 183 125 26 165 127 311 [出力例] 3042 |
■参照サイト
AtCoder Regular Contest 042