C++の練習を兼ねて, AtCoder Beginner Contest 255 の 問題C (±1 Operation 1) ~ 問題D (±1 Operation 2) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 255 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; int main(){ // 1. 入力情報. LL X, A, D, N; scanf("%lld %lld %lld %lld", &X, &A, &D, &N); // 2. 操作の最小回数は? // 2-1. 公差を調整. LL ans = 0; if(D < 0){ D = -D; A = A - D * (N - 1); } // 2-2. 公差ゼロ. if(D == 0){ printf("%lld\n", abs(A - X)); return 0; } // 2-3. 初項以下. if(X <= A){ printf("%lld\n", A - X); return 0; } // 2-4. 最終項以上. if(X >= A + D * (N - 1)){ printf("%lld\n", X - A - D * (N - 1)); return 0; } // 2-5. 上記以外. X -= A; X %= D; printf("%lld\n", min(X, D - X)); 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 |
[入力例] 6 2 3 3 [出力例] 1 ※AtCoderテストケースより [入力例] 0 0 0 1 [出力例] 0 ※AtCoderテストケースより [入力例] 998244353 -10 -20 30 [出力例] 998244363 ※AtCoderテストケースより [入力例] -555555555555555555 -1000000000000000000 1000000 1000000000000 [出力例] 444445 ※AtCoderテストケースより [入力例] 31 41 59 26 [出力例] 10 [入力例] 2022 6 13 255 [出力例] 1 |
■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 |
// 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 a[202020], aCum[202020]; int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); rep(i, N) scanf("%lld", &a[i]); // 2. sort. sort(a, a + N); // 3. 累積和. rep(i, N) aCum[i + 1] = aCum[i] + a[i]; // 4. クエリ回答. rep(i, Q){ // クエリ入力情報. LL x; scanf("%lld", &x); // 大小関係が変わる場所. int at = lower_bound(a, a + N, x) - a; // 集計. LL ans = 0; ans += (aCum[N] - aCum[at]) - x * (LL)(N - at); ans += x * (LL)at - aCum[at]; // 出力. 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 |
[入力例] 5 3 6 11 2 5 5 5 20 0 [出力例] 10 71 29 ※AtCoderテストケースより [入力例] 10 5 1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353 555555555 321654987 1000000000 789456123 0 [出力例] 3316905982 2811735560 5542639502 4275864946 4457360498 ※AtCoderテストケースより [入力例] 20 5 31 41 5 9 26 53 5 89 79 3 23 8 4 62 6 4 33 8 32 7 7 18 28 48 67 [出力例] 418 410 424 614 880 [入力例] 50 10 432 253 635 391 609 376 699 1147 868 743 1134 13 1020 170 377 224 63 1075 493 814 543 125 200 389 1111 971 1201 869 1008 553 1066 718 573 917 657 822 156 823 286 667 124 318 455 1208 399 251 190 74 1032 16 745 865 308 718 725 1362 753 1065 106 532 [出力例] 16834 19026 18192 16452 16550 38842 16962 24966 24474 15580 [入力例] 100 20 1803 8552 1725 9877 6771 9125 5772 11782 11128 12113 7042 10138 6032 9172 6314 3764 6937 1890 1272 9446 6824 2119 9519 9323 10070 4772 9204 348 2247 354 6407 11843 5199 8523 3456 10969 10723 8382 9282 5975 12204 2284 2439 8162 12288 1247 8208 8505 3083 7978 11199 3294 8426 1079 6657 10610 11825 1156 6909 4633 6636 90 12222 2226 6813 2537 6725 8666 8031 10913 9074 544 1337 8284 3677 4406 9826 10673 6716 3174 2796 11006 12305 9376 6602 7472 2588 11044 6210 3100 1661 8277 10858 9201 3965 11476 4149 5037 7017 5033 1500 1782 4834 5 5555 3867 510 777 24 534 4581 1334 92 2872 577 19 216 2990 165 999 [出力例] 532269 509501 347337 669623 325615 385395 620599 595967 667723 618343 356425 545887 660927 436063 614367 668223 648775 429219 653773 575543 |