C++の練習を兼ねて, AtCoder Beginner Contest 182 の 問題C (To 3) ～ 問題E (Akari) を解いてみた.
■感想.
1. 問題E は, 数え上げる方法が, 首尾よく見つかったので, AC版に到達できたと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 182 解説 の 各リンク を ご覧下さい.
■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 |
// 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--) int r[3]; int main(){ // 1. 入力情報. char n[33]; scanf("%s", n); string N(n); // 2. 各桁を3で割った場合の余り. rep(i, N.size()) r[(N[i] - '0') % 3]++; // 3. 3の倍数が作成できない場合. if(r[0] == 0){ if(r[1] + r[2] == 1){ puts("-1"); return 0; } if(r[1] == 0 && r[2] == 2){ puts("-1"); return 0; } if(r[1] == 2 && r[2] == 0){ puts("-1"); return 0; } } // 4. 最小の桁数は？ // -> 余り 0 は残す. // -> 余り 0 でない場合は, (1, 1, 1), (1, 2), (2, 2, 2) のような形で, 組み合わせる. int ans = 0; if(r[1] == 0) ans = r[2] % 3; if(r[2] == 0) ans = r[1] % 3; if(r[1] && r[2]){ if(r[1] % 3 == r[2] % 3) ans = 0; if(r[1] % 3 != r[2] % 3) ans = 1; } // 5. 出力. 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 |
[入力例] 35 [出力例] 1 ※AtCoderテストケースより [入力例] 369 [出力例] 0 ※AtCoderテストケースより [入力例] 6227384 [出力例] 1 ※AtCoderテストケースより [入力例] 11 [出力例] -1 ※AtCoderテストケースより |
■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 |
// 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--) LL aCum[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); LL ans = 0, cur = 0, aMax = 0; rep(i, N){ scanf("%lld", &aCum[i + 1]); // 累積和. aCum[i + 1] += aCum[i]; // 正方向の最大距離. aMax = max(aMax, aCum[i + 1]); // 更新. ans = max(ans, aMax + cur); // 現在位置. cur += aCum[i + 1]; } // 2. 出力. 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 |
[入力例] 3 2 -1 -2 [出力例] 5 ※AtCoderテストケースより [入力例] 5 -2 1 3 -1 -1 [出力例] 2 ※AtCoderテストケースより [入力例] 5 -1000 -1000 -1000 -1000 -1000 [出力例] 0 ※AtCoderテストケースより [入力例] 100 20022790 77312906 28502596 77179992 -76725463 21610710 25468798 -26917148 -69713598 -77687592 25158646 -47146999 82704774 61586512 19106570 63689620 -69024373 -66256411 1435505 -75172039 -80563839 37011095 68399099 -74796903 26525550 20414678 75195711 11845141 31908840 20765536 85858038 60077731 -81722174 -20753582 -14868082 70877005 -3169908 -7768198 60490382 1095223 48023286 -58861880 -24380265 42564919 26692705 -20007039 -3950337 -83339131 -83431162 77176199 51523492 31022813 230520 3974693 -7335799 -22624273 25760540 51004423 40920099 -72328969 -32148022 -17325796 -52872898 -81250143 57239096 61873344 37619949 -32512570 -56594056 20880843 24048391 18018645 -9478729 3819552 56463618 -66897726 -8255775 -52153846 55488291 49406848 -57371873 -27963618 53725101 46831927 -82985155 79609370 -37615012 -76230735 -61418017 -31474127 68616442 30205375 55514018 -87196634 -64488338 78424941 56321591 -73903849 79753422 74820465 [出力例] 18573336169 |
■C++版プログラム(問題E／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 |
// 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--) int o[1515][1515], lr[1515][1515], rl[1515][1515], ud[1515][1515], du[1515][1515]; int main(){ // 1. 入力情報. int H, W, N, M; scanf("%d %d %d %d", &H, &W, &N, &M); rep(i, N){ int a, b; scanf("%d %d", &a, &b); a--, b--; o[a][b] = 1; // 電球. } rep(i, M){ int c, d; scanf("%d %d", &c, &d); c--, d--; o[c][d] = -1; // ブロック. } // 2. 左右上下について, 電球の光が届いているか見る. // 2-1. 左 → 右. rep(i, H){ rep(j, W){ if(j) lr[i][j] += lr[i][j - 1]; if(o[i][j] == 1) lr[i][j] = 1; if(o[i][j] == -1) lr[i][j] = 0; } } // 2-2. 右 → 左. rep(i, H){ repr(j, W - 1, 0){ if(j < W - 1) rl[i][j] += rl[i][j + 1]; if(o[i][j] == 1) rl[i][j] = 1; if(o[i][j] == -1) rl[i][j] = 0; } } // 2-3. 上 → 下. rep(j, W){ rep(i, H){ if(i) ud[i][j] += ud[i - 1][j]; if(o[i][j] == 1) ud[i][j] = 1; if(o[i][j] == -1) ud[i][j] = 0; } } // 2-4. 下 → 上. rep(j, W){ repr(i, H - 1, 0){ if(i < H - 1) du[i][j] += du[i + 1][j]; if(o[i][j] == 1) du[i][j] = 1; if(o[i][j] == -1) du[i][j] = 0; } } // 3. カウント. int ans = 0; rep(i, H) rep(j, W) if(lr[i][j] + rl[i][j] + ud[i][j] + du[i][j]) ans++; // 4. 出力. 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 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 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 |
[入力例] 3 3 2 1 1 1 2 3 2 2 [出力例] 7 ※AtCoderテストケースより [入力例] 4 4 3 3 1 2 1 3 3 4 2 3 2 4 3 2 [出力例] 8 ※AtCoderテストケースより [入力例] 5 5 5 1 1 1 2 2 3 3 4 4 5 5 4 2 [出力例] 24 ※AtCoderテストケースより [入力例] 8 8 8 8 2 2 4 3 5 3 3 4 1 5 4 6 3 8 1 7 3 3 4 2 7 3 3 5 3 6 3 7 6 6 1 8 [出力例] 39 [入力例] 150 150 20 15 134 39 121 4 15 117 69 122 99 118 34 23 27 125 41 144 110 33 35 43 28 3 111 71 136 93 17 57 94 143 100 14 47 6 129 5 81 146 117 20 51 6 125 17 48 75 49 20 142 146 34 90 19 43 116 132 35 114 86 120 98 97 93 90 31 137 75 26 10 123 [出力例] 5362 [入力例] 200 200 100 60 11 130 128 17 117 49 75 69 53 28 150 30 73 4 64 47 14 10 127 140 84 112 143 110 118 61 107 73 85 113 144 65 111 23 82 10 14 145 47 101 128 33 51 117 13 89 111 62 101 20 41 88 15 95 115 78 5 141 6 133 106 76 23 83 144 50 130 92 141 81 124 79 31 17 58 63 130 53 38 62 63 92 57 13 8 109 90 82 144 85 144 90 1 27 48 55 105 92 45 111 143 97 31 123 74 131 136 86 88 95 44 112 99 147 148 61 109 12 2 119 84 57 81 123 104 48 90 63 120 50 130 25 111 149 112 137 119 19 134 100 105 8 78 84 143 126 30 51 115 74 52 55 137 56 97 127 130 29 64 42 21 141 132 70 58 21 30 101 85 63 25 38 62 16 86 31 1 65 150 9 135 134 74 18 47 127 57 50 46 102 28 138 125 31 39 115 6 148 16 99 104 13 17 104 44 57 123 110 82 134 117 4 115 117 8 100 74 111 76 118 90 45 22 40 109 63 129 96 44 25 80 116 144 66 74 28 16 9 25 7 109 125 51 103 81 141 4 138 121 39 100 34 53 42 84 65 136 139 89 5 97 90 42 112 132 132 80 62 85 84 10 89 7 119 128 129 12 43 12 91 6 23 120 49 121 63 36 29 50 95 139 1 98 77 15 8 40 86 71 73 60 88 129 63 75 48 24 110 141 150 22 150 22 25 81 4 94 75 132 95 [出力例] 22513 [入力例] 500 500 189 111 443 34 139 424 222 301 368 353 451 352 132 271 191 232 456 338 446 443 210 105 145 318 259 270 284 51 350 354 468 353 137 208 441 270 218 28 146 203 116 197 372 288 47 417 462 191 132 45 344 154 178 322 32 286 295 449 203 351 380 287 445 455 67 298 281 54 492 477 162 74 256 451 171 397 367 167 258 375 42 339 256 418 43 401 79 404 485 194 5 175 269 342 90 206 288 238 481 383 379 365 19 17 255 420 182 255 227 357 82 138 163 170 118 121 3 108 498 370 297 143 196 455 3 481 227 309 209 309 171 311 128 210 309 213 20 361 477 303 357 110 166 461 383 254 53 459 58 416 157 108 52 133 288 482 414 271 207 126 86 140 134 336 103 50 155 273 38 303 65 217 4 232 191 21 164 433 276 172 465 374 255 449 179 84 156 375 123 50 158 236 335 383 477 403 314 46 440 71 198 249 493 77 210 158 146 449 232 360 108 38 101 119 104 225 299 199 346 300 422 221 45 209 294 334 242 137 137 325 389 208 196 453 42 340 414 25 493 148 40 166 438 485 233 470 136 430 168 280 298 76 19 491 261 309 381 410 475 327 272 97 431 420 370 29 34 27 264 211 163 53 434 260 454 555 103 73 422 401 69 218 492 236 29 379 380 294 364 166 227 296 379 8 209 85 254 407 79 312 307 394 125 76 467 174 146 342 319 178 465 442 112 286 486 236 110 224 396 269 4 177 329 45 157 354 472 93 16 302 241 45 144 219 26 55 236 78 178 253 161 295 257 114 13 338 257 210 417 15 145 233 205 13 227 425 215 354 127 151 344 268 362 267 187 388 272 445 238 488 38 289 335 151 192 494 134 348 271 174 374 373 399 157 190 427 231 18 33 357 419 347 279 29 126 491 272 53 36 202 465 294 100 198 20 482 78 201 481 262 321 244 46 316 382 357 290 137 275 398 25 389 32 14 75 26 138 238 486 352 210 168 118 272 271 106 369 394 346 52 193 383 135 356 264 91 498 426 460 433 382 373 72 475 477 44 456 254 30 390 122 430 17 500 121 127 258 240 64 16 59 311 408 428 450 470 447 305 71 343 468 377 140 276 338 282 133 348 332 342 471 359 250 22 243 59 236 34 404 202 330 351 119 14 307 233 164 488 206 95 45 56 275 265 98 420 127 398 319 453 47 65 230 490 467 128 95 28 387 261 298 59 430 378 378 115 299 191 353 59 145 39 79 15 16 184 458 235 421 138 10 211 377 420 424 79 384 91 300 405 172 253 189 215 177 441 48 341 131 395 198 11 264 245 67 94 2 1 496 166 204 447 471 412 327 157 219 140 484 81 365 364 121 462 455 254 117 50 494 210 52 473 [出力例] 123613 |
■参照サイト
AtCoder Beginner Contest 182