C++の練習を兼ねて, AtCoder Beginner Contest 323 の 問題C (World Tour Finals) ~ 問題D (Merge Slimes) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D で, スライム合成の繰り返す処理が, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 323 解説 の 各リンク を ご覧下さい.
■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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
// C++20(GCC 12.2) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using vs = vector<string>; #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() int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vi a(M); rep(i, M) scanf("%d", &a[i]); vs s(N); rep(i, N){ char c[202]; scanf("%s", c); string b(c); s[i] = b; } // 2. 各プレイヤーの現在の総合得点は? vi scores(N, 0); rep(i, N){ scores[i] = i + 1; rep(j, M) scores[i] += a[j] * (s[i][j] == 'o'); } // 3. 各プレイヤーが解いてない問題の各得点は? vvi notSolved(N); rep(i, N){ rep(j, M) if(s[i][j] == 'x') notSolved[i].pb(a[j]); sort(all(notSolved[i])); reverse(all(notSolved[i])); } // 4. 他プレイヤーの現在の総合得点の最大値は? vi maxScoreOnOtherPlayers(N, 0); rep(i, N){ int maxScore = 0; rep(j, N) if(i != j) maxScore = max(maxScore, scores[j]); maxScoreOnOtherPlayers[i] = maxScore; } // 5. 出力. rep(i, N){ int ans = 0; int cur = scores[i]; for(auto &p : notSolved[i]){ if(maxScoreOnOtherPlayers[i] >= cur){ ++ans; cur += p; } } 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 71 72 73 74 75 76 77 78 |
[入力例] 3 4 1000 500 700 2000 xxxo ooxx oxox [出力例] 0 1 1 ※AtCoderテストケースより [入力例] 5 5 1000 1500 2000 2000 2500 xxxxx oxxxx xxxxx oxxxx oxxxx [出力例] 1 1 1 1 0 ※AtCoderテストケースより [入力例] 7 8 500 500 500 500 500 500 500 500 xxxxxxxx oxxxxxxx ooxxxxxx oooxxxxx ooooxxxx oooooxxx ooooooxx [出力例] 7 6 5 4 3 2 0 ※AtCoderテストケースより [入力例] 3 5 500 500 1000 1000 2500 xxxxo xxxox xooxx [出力例] 0 1 1 [入力例] 5 7 500 500 500 500 1000 1000 1500 ooxooxx xoxxxxx xxxxxxx xxooxox ooxxoxo [出力例] 1 3 4 2 0 |
■C++版プログラム(問題D/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 |
// C++20(GCC 12.2) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using P = pair<LL, LL>; 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 a first #define b second #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; scanf("%d", &N); vp slimes(N); rep(i, N) scanf("%lld %lld", &slimes[i].a, &slimes[i].b); // 2. sort. sort(all(slimes)); // 3. スライムの合成. map<LL, LL> m; rep(i, N){ // 初期化(スライムのサイズ, 匹数). LL slimeSize = slimes[i].a; LL slimeCount = slimes[i].b; // 前回以前を反映. if(m.count(slimes[i].a)) slimeCount += m[slimes[i].a]; else m[slimes[i].a] = slimes[i].b; // 合成対象のスライム匹数が, 0匹になるまで, 繰り返し. while(slimeCount){ // スライム出現. m[slimeSize * 2] += slimeCount / 2; // スライム消滅. m[slimeSize] = slimeCount % 2; // 更新(スライムのサイズ, 匹数). slimeSize *= 2; slimeCount = m[slimeSize]; } } // 4. 集計. LL ans = 0; for(auto &x : m) ans += x.b; // 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 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 215 216 217 218 219 220 221 222 |
[入力例] 3 3 3 5 1 6 1 [出力例] 3 ※AtCoderテストケースより [入力例] 3 1 1 2 1 3 1 [出力例] 3 ※AtCoderテストケースより [入力例] 1 1000000000 1000000000 [出力例] 13 ※AtCoderテストケースより [入力例] 5 1 3 2 2 3 1 4 5 8 2 [出力例] 5 [入力例] 10 11 4 3 1 12 9 2 10 10 10 5 2 7 6 15 2 24 3 8 1 [出力例] 15 [入力例] 20 19 81 8 52 7 104 3 94 14 26 16 47 1 46 6 108 11 113 20 52 5 105 15 5 18 95 17 20 10 121 4 53 12 65 9 14 2 15 13 96 [出力例] 36 [入力例] 30 14 929755 10 812758 26 405849 5 775226 19 916477 13 786895 17 119046 30 492339 7 429931 1 267396 11 892144 24 812785 20 480207 2 516830 25 749069 18 430046 6 653612 22 1122701 28 336222 29 1020713 27 203310 12 441113 21 729150 9 414670 8 432888 23 510440 15 250019 4 956264 16 239998 3 783368 [出力例] 157 [入力例] 100 63 802 2 1186 54 547 22 466 95 387 41 615 90 1071 76 1087 74 1017 27 877 30 704 86 1126 82 286 68 348 37 30 11 128 100 824 48 720 1 870 9 794 38 188 17 646 24 844 99 8 23 1017 18 209 8 661 83 243 50 766 87 1030 65 406 66 632 53 299 69 843 4 232 29 152 81 819 85 1064 97 80 14 526 71 470 75 816 13 22 42 217 33 188 93 898 10 721 40 780 44 1078 84 31 98 468 60 816 45 585 91 404 61 1176 28 389 36 913 51 472 94 1203 88 472 57 1130 73 1183 12 788 62 691 5 1056 43 330 46 406 19 708 67 1213 55 983 96 30 52 817 21 1049 32 1178 92 1202 70 19 6 373 35 450 25 112 15 434 72 858 3 706 79 238 26 312 34 521 49 112 56 51 7 474 78 631 31 242 59 231 20 1049 80 678 64 906 39 286 58 106 77 473 89 233 16 1168 47 591 [出力例] 278 |
■参照サイト
ユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)