C++の練習を兼ねて, 競プロ典型 90 問 の 問題056 (Lucky Bag) を解いてみた.
■感想.
1. 問題056は, 過去問 AtCoder Beginner Contest 204 (D – Cooking)に類似した方針で解けそうと気付けたので, AC版に到達出来たと思う.
2. 個人的には, 福袋の選択パターンを, 動的計画法を用いて, 計算量を削減出来る点が, 非常に面白いと感じた.
3. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題056 を ご覧下さい.
■C++版プログラム(問題056／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 71 72 73 74 75 76 77 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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 int a[111], b[111], d[111], dp[101010], cost[101010]; int main(){ // 1. 入力情報. int N, S, tMin = 0, tMax = 0; scanf("%d %d", &N, &S); string ans = ""; rep(i, N){ scanf("%d %d", &a[i], &b[i]); if(a[i] <= b[i]) ans.pb('A'); else ans.pb('B'); tMin += min(a[i], b[i]); tMax += max(a[i], b[i]); d[i] = abs(a[i] - b[i]); } // 2. NGパターン. if(S < tMin || S > tMax){ puts("Impossible"); return 0; } // 3. OKパターン. S -= tMin; if(S == 0){ printf("%s\n", ans.c_str()); return 0; } // 4. 福袋(金額差分) を 割り当てを探索. // -> 最小となる場合の福袋の割り当ては完了しているので, // 福袋のいずれかを, 金額の大きい方に変更して, // S円とすることが出来るかをチェック. dp[0] = 1; rep(i, N){ repr(j, S, 0){ // i番目の福袋(金額差分)を考慮. int cur = d[i] + j; if(cur <= S && dp[j]){ // dp更新. dp[cur] = 1; // 未訪問の場合, 福袋の番号を記録. if(!cost[cur]) cost[cur] = i + 1; // 1-index. } } } // 5. NGパターン. if(!cost[S]){ puts("Impossible"); return 0; } // 6. 福袋(金額差分) を 割り当てる. int cur = S; while(cur > 0){ int idx = cost[cur] - 1; // 0-index. char c = ans[idx]; ans[idx] = (c == 'B') ? 'A' : 'B'; cur -= d[idx]; } // 7. 出力. printf("%s\n", ans.c_str()); 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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
[入力例] 3 34 3 14 15 9 26 5 [出力例] BAB ※AtCoderテストケースより [入力例] 5 77 1 16 3 91 43 9 4 26 23 11 [出力例] BABBA ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. BAAAB [入力例] 5 59 8 13 55 5 58 8 23 14 4 61 [出力例] Impossible ※AtCoderテストケースより [入力例] 3 15 2 7 5 6 8 10 [出力例] AAA [入力例] 5 39 2 12 5 6 8 9 1 5 3 7 [出力例] BBBBB [入力例] 10 543 110 44 94 93 31 22 15 79 49 70 50 28 79 104 23 51 11 112 79 110 [出力例] ABAAABBAAA [入力例] 15 2021 132 79 176 6 196 110 11 94 95 150 150 235 309 49 104 103 284 92 214 159 73 207 288 216 294 132 210 138 143 319 [出力例] ABAAAABBABBBBBA [入力例] 25 54321 1382 4941 2128 4730 1776 4176 3947 1801 5307 1004 4280 433 3821 3670 2846 561 1308 1481 4009 2258 2159 1647 379 1766 1237 2114 1778 165 5537 4890 4815 4662 2005 1702 3112 3967 1311 2497 52 1929 3137 4904 3088 3898 3697 5289 3842 4282 1843 4741 [出力例] AABBBBABBBAAABBBBAAAAAAAA |
■参照サイト
056 – Lucky Bag
AtCoder Beginner Contest 204 (D – Cooking)