C++の練習を兼ねて, AtCoder Beginner Contest 169 の 問題F (F – Knapsack for All Subsets) を解いてみた.
■感想.
1. 解答方針が, 全く見えなかったので, 解答を参照して実装した.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 169 解説をご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/abc169/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) const LL MOD = 998244353; LL dp[3030][3030], a[3030], memo[3030], mPow2[3030]; int main(){ // 1. 入力情報. int N, S; scanf("%d %d", &N, &S); rep(i, N) scanf("%lld", &a[i]); // 2. 2 の べき乗 を 保存. mPow2[0] = 1; repx(i, 1, 3030) mPow2[i] = mPow2[i - 1] * 2, mPow2[i] %= MOD; // 3. dp更新. repx(i, 1, N + 1){ repr(j, S, 0){ int d = j - (int)a[i - 1]; if(d > 0 && memo[d]) dp[i][j] += dp[i - 1][d], dp[i][j] %= MOD, memo[j]++; if(d == 0) dp[i][j] += mPow2[i - 1], memo[j]++; dp[i][j] += dp[i - 1][j] * 2; dp[i][j] %= MOD; } } // 4. 出力. printf("%lld\n", dp[N][S]); 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 |
[入力例] 3 4 2 2 4 [出力例] 6 ※AtCoderテストケースより [入力例] 5 8 9 9 9 9 9 [出力例] 0 ※AtCoderテストケースより [入力例] 10 10 3 1 4 1 5 9 2 6 5 3 [出力例] 3296 ※AtCoderテストケースより [入力例] 5 7 1 2 3 3 4 [出力例] 24 [入力例] 7 12 1 2 5 3 10 7 8 [出力例] 96 [入力例] 15 17 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 [出力例] 806912 [入力例] 100 1234 37 97 66 35 28 118 7 100 81 73 60 114 99 70 12 64 104 26 86 34 66 35 46 73 96 61 76 2 53 47 18 91 25 91 104 41 92 29 32 109 68 41 21 85 65 115 99 105 36 56 75 75 32 34 58 79 14 63 10 9 55 123 61 51 46 94 55 92 51 96 86 112 96 97 90 56 70 59 120 56 102 99 24 56 28 42 101 101 61 31 26 41 39 8 70 74 12 75 97 44 [出力例] 329849245 |
■参照サイト
AtCoder Beginner Contest 169