C++の練習を兼ねて, AtCoder Beginner Contest 226 の 問題G (The baggage) を解いてみた.
■感想.
1. 問題Gは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 荷物の重さと, 人の体力に応じて, 割り当てを決めていくロジックが, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 226 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題G／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 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 125 126 127 |
// 解き直し. // https://atcoder.jp/contests/abc226/editorial/2893 // 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--) int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. 各テストケース. rep(i, T){ // 2-1. テストケース. LL a[5], b[5], r[5], o; rep(j, 5) scanf("%lld", &a[j]); // 荷物. rep(j, 5) scanf("%lld", &b[j]); // 体力. // 2-2. Step1. // -> 体力 5 の 人 が, 重さ 5 の 荷物 を持つ. o = min(a[4], b[4]); a[4] -= o; b[4] -= o; // 2-3. Step2. // -> 体力 4 の 人 が, 重さ 4 の 荷物 を持つ. o = min(a[3], b[3]); a[3] -= o; b[3] -= o; // 2-4. Step3. // -> 体力 5 の 人 が, 重さ 4 の 荷物 を持つ. o = min(a[3], b[4]); b[0] += o; // 残り体力 1 の 人 を 増やす. a[3] -= o; b[4] -= o; // 2-5. Step4. // -> 体力 3 の 人 が, 重さ 3 の 荷物 を持つ. o = min(a[2], b[2]); a[2] -= o; b[2] -= o; // 2-6. Step5. // -> 体力 5 の 人 が, 重さ 3 の 荷物 を持つ. o = min(a[2], b[4]); b[1] += o; // 残り体力 2 の 人 を 増やす. a[2] -= o; b[4] -= o; // 2-7. Step6. // -> 体力 4 の 人 が, 重さ 3 の 荷物 を持つ. o = min(a[2], b[3]); b[0] += o; // 残り体力 1 の 人 を 増やす. a[2] -= o; b[3] -= o; // 2-8. Step7. // -> 残り体力 2以上 の 人 が, 重さ 2 の 荷物 を持つ. // 残り体力 5. o = min(a[1], b[4]); b[2] += o; // 残り体力 3 の 人 を 増やす. a[1] -= o; b[4] -= o; // 残り体力 4. o = min(a[1], b[3]); b[1] += o; // 残り体力 2 の 人 を 増やす. a[1] -= o; b[3] -= o; // 残り体力 3. o = min(a[1], b[2]); b[0] += o; // 残り体力 1 の 人 を 増やす. a[1] -= o; b[2] -= o; // 残り体力 2. o = min(a[1], b[1]); a[1] -= o; b[1] -= o; // 2-9. Step8. // -> 残り体力 1以上 の 人 が, 重さ 1 の 荷物 を持つ. // 残り体力 5. o = min(a[0], b[4]); b[3] += o; // 残り体力 4 の 人 を 増やす. a[0] -= o; b[4] -= o; // 残り体力 4. o = min(a[0], b[3]); b[2] += o; // 残り体力 3 の 人 を 増やす. a[0] -= o; b[3] -= o; // 残り体力 3. o = min(a[0], b[2]); b[1] += o; // 残り体力 2 の 人 を 増やす. a[0] -= o; b[2] -= o; // 残り体力 2. o = min(a[0], b[1]); b[0] += o; // 残り体力 1 の 人 を 増やす. a[0] -= o; b[1] -= o; // 残り体力 1. o = min(a[0], b[0]); a[0] -= o; b[0] -= o; // 2-10. 出力. LL ans = 0; rep(j, 5) ans += a[j]; printf("%s\n", ans ? "No" : "Yes"); } 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 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 |
[入力例] 3 5 1 0 0 1 0 0 0 2 1 0 3 0 0 0 0 0 2 0 0 10000000000000000 0 0 0 0 0 0 0 0 2000000000000000 [出力例] Yes No Yes ※AtCoderテストケースより [入力例] 5 5 4 3 2 1 4 2 2 4 1 6 5 4 3 2 2 1 3 6 3 7 6 5 4 3 1 6 4 5 4 8 7 6 5 4 0 9 3 6 6 9 8 7 6 5 3 6 9 7 5 [出力例] Yes Yes Yes Yes Yes [入力例] 15 9 3 5 0 1 3 7 0 1 10 3 0 1 3 5 4 10 11 3 1 1 1 6 11 11 2 5 7 6 7 0 4 10 3 3 11 11 9 8 9 10 7 8 11 1 1 3 10 9 3 5 8 8 9 0 10 8 10 10 5 9 0 6 3 0 1 5 5 8 4 0 2 2 1 9 4 2 6 3 10 1 1 8 3 9 3 2 1 7 0 10 0 9 7 9 3 1 11 7 8 9 8 6 3 1 9 2 7 10 11 6 6 5 9 4 3 10 0 8 10 2 0 10 11 1 5 8 3 5 7 5 8 6 8 9 5 5 4 11 10 0 6 11 4 9 2 3 8 3 13 [出力例] Yes No No Yes No Yes Yes Yes No No Yes Yes No Yes Yes [入力例] 30 4736 652 4583 6377 1597 8938 11245 5687 2942 1669 5463 1542 5058 2635 6214 7208 129 10478 10210 7131 3444 3342 3013 810 1573 363 1159 4324 99 1684 4683 6063 910 1382 7313 8436 2778 8775 3803 7507 4719 4910 8740 3752 8851 11313 2566 10001 9487 8976 8823 5515 9340 11275 10231 9358 2676 2884 451 2384 4857 3539 2594 4775 3193 3007 2610 4228 10693 3277 4608 4158 11708 6559 3383 2359 2399 6914 1167 4975 8141 4933 5370 2458 4976 1670 1881 2905 1144 1017 11820 8030 3539 8741 1074 209 5655 5606 4350 2281 174 8883 3762 7666 2423 12244 2773 2089 10577 3312 363 694 9803 6172 3573 5009 8611 11 3200 6165 3653 9811 6193 508 5619 5646 11988 6557 10264 7174 7962 1308 3615 9979 7739 1514 8295 10587 776 10807 5104 58 274 2361 11025 9355 225 7506 10287 11062 5367 9615 7668 7538 10932 371 1729 2728 10289 11516 8743 10524 6069 8198 10158 2925 6812 4133 11672 11499 2503 11237 2692 577 10567 3170 1318 9652 2333 10572 5369 1267 8608 2146 9466 3422 7021 5493 3181 9636 6025 4947 11230 3907 1864 1877 11256 1516 793 1997 1577 2439 8331 8472 4652 5496 723 4187 6943 4853 1773 11463 634 2337 1877 985 7083 11433 5979 1997 8012 1682 11478 3820 5897 5654 12342 3699 8523 5996 7786 3524 3335 6034 9057 3193 11703 10927 9535 9948 2676 480 7916 5608 9541 4481 1611 9242 6065 9740 1241 9799 3907 437 6700 9516 7654 1774 9564 8078 1462 723 2367 3068 7547 10838 361 10818 11597 7606 7872 4023 8552 5344 5425 1414 12181 2373 3322 6531 3928 10822 4620 2205 5016 1788 825 1998 11854 7000 7980 10848 3678 593 6726 9115 7408 6206 10854 6732 [出力例] No Yes No Yes Yes No Yes No No No No No Yes No Yes No Yes Yes No No No Yes No Yes Yes Yes Yes No Yes Yes [入力例] 10 507748368 726522441 716842295 896598460 320433421 807756860 1178694558 696537829 675310808 321433525 1100909478 52594898 732721689 103256278 673683127 491553713 300979021 676273796 175896042 673693246 733173811 157956974 318073620 1203738633 103785639 574388248 204673136 539204115 1293133539 103788739 797087955 846601242 160116906 647766959 1164301869 84091606 868364510 1139454715 309964343 1164301884 467107126 467648868 300152068 23853124 708038233 192141104 1014838572 217300457 575553789 708038242 406340697 1217472541 176376639 1057125688 838469709 316724026 430450759 862185393 569966560 838469747 770761652 169240487 470842492 261863093 144541641 619970914 889107620 228698634 972783556 144541683 199041083 986396475 933182708 881589693 265895695 509144341 28749492 1164256597 972818486 265895787 1064560339 275860069 734979313 470598359 499844092 589489072 264860113 1187179191 738120897 499844130 176821395 342098591 214641446 636905853 801658981 552727141 433876986 568539870 870496264 801659031 [出力例] No Yes Yes No Yes No Yes No Yes Yes |
■参照サイト
AtCoder Beginner Contest 226