C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題F (Max Sum Counting) を解いてみた.
■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 216 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F/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 |
// 解き直し. // https://atcoder.jp/contests/abc216/editorial/2560 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<int, int>; using vp = vector<P>; #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 all(x) x.begin(), x.end() #define a first #define b second const LL MOD = 998244353; LL dp[5050][5050], a[5050], b[5050]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); rep(i, N) scanf("%d", &b[i]); // 2. sort. vp v; rep(i, N) v.pb({a[i], b[i]}); sort(all(v)); // 3. dp更新. // Typical DP Contest (A - コンテスト) を ベース に 実装. // https://atcoder.jp/contests/tdpc/tasks/tdpc_contest dp[0][0] = 1; repx(i, 1, N + 1){ // 前回分反映. rep(j, 5000) dp[i][j] += dp[i - 1][j]; // 今回分反映. repr(j, 5000, 0){ if(j + v[i - 1].b <= 5000){ dp[i][j + v[i - 1].b] += dp[i][j]; dp[i][j + v[i - 1].b] %= MOD; } } } // 4. 集計. LL ans = 0; // 並び替え前の情報を使っていたので, index も含めて, ロジック修正(000.txt などで, WA版となった). // repx(i, 1, N + 1){ // rep(j, a[i - 1] - b[i - 1] + 1){ rep(i, N){ rep(j, v[i].a - v[i].b + 1){ ans += dp[i][j]; ans %= MOD; } } // 5. 出力. 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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
[入力例] 2 3 1 1 2 [出力例] 2 ※AtCoderテストケースより [入力例] 2 1 1 2 2 [出力例] 0 ※AtCoderテストケースより [入力例] 20 1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247 4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017 [出力例] 476 ※AtCoderテストケースより [入力例] 5 11 7 8 10 1 8 8 5 4 1 [出力例] 9 [入力例] 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 9 50 28 84 19 71 69 39 93 75 10 58 20 97 49 44 59 2 30 78 16 40 62 86 20 89 98 62 80 34 82 53 42 11 70 67 98 21 4 80 86 51 32 82 30 66 4 70 [出力例] 858 [入力例] 50 24 65 106 21 21 8 21 93 35 83 20 21 18 104 82 13 74 53 26 84 94 97 120 44 117 115 109 26 123 11 18 54 106 53 53 79 57 111 29 92 26 25 65 28 55 86 11 76 19 74 14 8 115 35 57 118 76 48 7 41 63 49 41 29 10 51 95 47 95 4 36 106 108 115 70 116 48 62 58 39 81 66 101 53 17 68 73 35 90 9 111 91 20 64 4 96 39 101 30 123 [出力例] 11620 [入力例] 100 1540 1174 910 995 418 1478 131 730 2216 1677 1056 704 648 1114 794 276 1839 297 2082 83 566 913 458 1788 1528 287 281 1475 1998 570 1319 1719 1752 1008 88 953 599 235 1229 2067 1064 1590 306 1747 756 1277 146 1367 539 725 2139 1061 617 395 1947 194 703 100 441 1979 631 1717 1619 463 275 1283 1433 1788 1309 48 867 1758 997 37 1951 54 106 71 1621 1051 1502 1783 593 1097 900 249 511 934 944 1099 1826 1080 1430 1175 486 1056 2202 700 569 1914 1445 1448 56 875 681 807 1791 707 397 1056 1073 866 2079 598 722 1514 490 788 196 93 607 769 685 851 475 703 1924 1606 1414 1291 96 1641 1717 1500 852 1995 1198 469 122 619 2123 1417 277 1321 658 1783 855 1653 1938 752 1011 223 1134 1616 2032 2009 75 1369 114 1775 2126 549 1691 778 412 1636 1404 1822 822 1997 821 168 315 263 529 65 142 393 2090 1871 1385 1702 963 1838 1513 619 1996 1788 1750 180 35 1231 846 24 1355 1463 1354 885 582 674 [出力例] 10146452 |
■参照サイト
AtCoder Beginner Contest 216