C++の練習を兼ねて, AtCoder Regular Contest 158 の 問題A (+3 +5 +7) ～ 問題C (All Pair Digit Sums) を解いてみた.
■感想.
1. 問題A ～ C は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 問題C で, 尺取り法 の 復習ができたので 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 158 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A／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 |
// 解き直し. // https://atcoder.jp/contests/arc158/editorial/5902 // 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 x1, x2, x3; scanf("%lld %lld %lld", &x1, &x2, &x3); // 2-2. 例外(その①). LL a = x1 + x2 + x3; if(a % 3 != 0){ puts("-1"); continue; } // 2-3. 例外(その②). a /= 3; if(!((a % 2 == x1 % 2) && (a % 2 == x2 % 2) && (a % 2 == x3 % 2))){ puts("-1"); continue; } // 2-4. 最小の操作回数は？ printf("%lld\n", (abs(x1 - a) + abs(x2 - a) + abs(x3 - a)) / 4); } 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 |
[入力例] 4 2 8 8 1 1 1 5 5 10 10 100 1000 [出力例] 2 0 -1 315 ※AtCoderのテストケースより [入力例] 10 57 27 87 31 41 51 92 18 46 101 131 191 333 555 777 300 600 900 27 106 56 88 148 208 78 76 121 20 4 84 [出力例] 15 5 20 25 111 150 -1 30 -1 24 |
■C++版プログラム(問題B／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 |
// 解き直し. // https://atcoder.jp/contests/arc158/editorial/5903 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #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[2020202]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vi X; rep(i, N){ int x; scanf("%d", &x); if(N < 6) X.pb(x); x += 1e6; ++a[x]; } // 2. 小さい方から三つ. vi vMin; repr(i, 1e6 - 1, 0) rep(j, a[i]) if(vMin.size() < 3) vMin.pb(i - 1e6); repr(i, 2e6, 1e6 + 1) rep(j, a[i]) if(vMin.size() < 3) vMin.pb(i - 1e6); // for(auto &p : vMin) printf("%d\n", p); // 3. 大きい方から三つ. vi vMax; repx(i, 1e6 + 1, 2e6 + 1) rep(j, a[i]) if(vMax.size() < 3) vMax.pb(i - 1e6); rep(i, 1e6) rep(j, a[i]) if(vMax.size() < 3) vMax.pb(i - 1e6); // for(auto &p : vMax) printf("%d\n", p); // 4. 多重集合 X. if(!X.size()){ for(auto &p : vMin) X.pb(p); for(auto &p : vMax) X.pb(p); } // 5. 最小値, 最大値は？ int n = X.size(); double aMin = +2020202020202020202.0; double aMax = -2020202020202020202.0; rep(i, n){ rep(j, n){ rep(k, n){ if(i != j && j != k && k != i){ double cur = (double)(X[i] + X[j] + X[k]); cur /= (double)(X[i]); cur /= (double)(X[j]); cur /= (double)(X[k]); aMin = min(aMin, cur); aMax = max(aMax, cur); } } } } // 6. 出力. printf("%.15lf\n%.15lf\n", aMin, aMax); 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 |
[入力例] 4 -2 -4 4 5 [出力例] -0.175000000000000 -0.025000000000000 ※AtCoderのテストケースより [入力例] 4 1 1 1 1 [出力例] 3.000000000000000 3.000000000000000 ※AtCoderのテストケースより [入力例] 5 1 2 3 4 5 [出力例] 0.200000000000000 1.000000000000000 ※AtCoderのテストケースより [入力例] 10 3 1 4 1 5 9 2 6 5 3 [出力例] 0.074074074074074 2.000000000000000 [入力例] 25 -62654 38060 -40395 73411 32287 -31964 -6069 -59569 -18953 18276 -81815 84325 23611 65481 19093 -68288 76696 84093 66270 91521 -64748 -14904 -17338 58638 95110 [出力例] -0.000000014779913 0.000000024428934 [入力例] 100 69916 -958462 175350 663506 174976 381343 837499 -218757 486796 -109940 -387930 116682 869009 215328 -85009 -817691 581748 711432 -170442 707919 14179 -463495 -476948 -673290 -913092 11249 -189868 -746976 505087 -622496 849045 838323 716835 784815 -185511 -4073 -951883 -370116 -911945 74817 -767359 769381 104268 -176164 -571565 605559 -678942 -324080 133562 -79780 94243 852129 -250020 578113 -197780 613104 714339 320649 323447 743163 420709 299303 -793398 258040 -46584 -164749 656078 859105 355055 126428 410186 988732 -504969 200275 770031 -63896 -147531 418090 274663 -796636 36168 217126 -254489 709912 44747 281016 -499495 709992 212867 -218466 349600 -60391 -466757 -743023 259071 24453 -888436 -138187 246464 788471 [出力例] -0.000000032871964 0.000000012789203 |
■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 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 |
// 解き直し. // https://atcoder.jp/contests/arc158/editorial/5904 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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() LL a[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); LL aMax = 0; rep(i, N){ scanf("%lld", &a[i]); aMax = max(aMax, a[i]); } // 2. f. auto f = [&](LL n) -> LL { LL ret = 0; assert(n >= 0); while(n){ ret += n % 10; n /= 10; } return ret; }; // 3. 合計. LL ans = 0; rep(i, N) ans += f(a[i]) * 2 * N; // 4. 最大桁数 K. int K = 0; while(aMax){ ++K; aMax /= 10; } // 5. 桁上がり分 を 集計. LL carry = 0, d = 1; rep(k, K){ // 10 の (k + 1)乗. d *= 10; // 余り x[i]. vl x; rep(i, N) x.pb(a[i] % d); // sort. sort(all(x)); // 尺取り法. int cur = N - 1; rep(l, N){ // 右側. int s = cur; repr(r, s, l){ // 更新. cur = r; // 桁上がりが見つかった. if(x[l] + x[r] >= d) continue; // 次へ. break; } // 桁上がり分を加算. if(l < cur) carry += 2 * (N - 1 - cur); // 終了条件. if(l >= cur){ // 桁上がり分を加算. carry += (LL)(N - cur) * (LL)(N - cur); if(x[l] + x[cur] < d) --carry; // 終了. break; } } } // 6. 桁上がり分 を 減算. ans -= carry * 9; // 7. 出力. 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 |
[入力例] 2 53 28 [出力例] 36 ※AtCoderのテストケースより [入力例] 1 999999999999999 [出力例] 135 ※AtCoderのテストケースより [入力例] 5 123 456 789 101 112 [出力例] 321 ※AtCoderのテストケースより [入力例] 10 877 2585 7531 11636 5407 10490 2919 4532 11968 6571 [出力例] 1826 [入力例] 20 2393459 2597592 9505071 7781639 3941269 11574647 10141029 7729956 5040599 7776400 4374539 4798162 1267669 959174 1602926 892360 3494352 8402891 4887639 9792278 [出力例] 13238 [入力例] 100 106830287 96297137 99507332 120542676 12480615 7988160 102303598 43518574 49587435 94374908 7640495 88460951 118398168 61221541 113945917 105266591 88283842 99682740 75784384 27248820 46611683 63624340 3243101 74574568 60575314 42966526 119849902 110794016 114392684 110470545 96730113 119821124 123444633 109708206 83442219 49800640 87862787 21189091 91254742 52378699 118374037 77594928 63008973 13058689 79673135 14169600 43908552 71245022 101211144 31151792 101626330 50762445 32103874 117480389 68620838 44935862 40259456 104169855 84453646 80701603 67655779 2143857 116506450 60053024 7312992 94662630 57846804 89395004 16571557 98434911 74528701 23929873 66957073 41170766 75800861 100453435 51092328 6798915 46133408 84964698 50926294 70015591 91551909 105928166 63985408 93857936 31874447 62932675 67370594 7590564 67516487 69931336 18257230 63202372 37661017 32950199 53732043 60295509 62016818 93710886 [出力例] 367109 [入力例] 300 103 105 82 73 36 50 55 73 15 104 40 115 41 50 57 94 77 48 37 33 47 123 9 54 102 90 42 79 18 95 88 60 40 52 116 75 122 120 101 61 33 60 55 113 117 76 38 61 91 40 100 109 102 84 25 74 80 87 15 91 22 80 33 32 23 86 47 7 116 60 93 112 103 89 102 108 81 2 106 103 39 119 19 6 66 69 107 36 37 34 108 119 93 36 62 78 34 98 106 64 52 102 56 60 55 88 100 17 14 38 103 87 84 73 61 24 20 56 104 74 184 36 47 50 30 54 91 58 63 104 18 99 61 41 53 55 34 3 19 115 96 98 3 114 60 97 51 43 78 27 61 116 88 18 73 12 75 75 78 37 42 64 92 73 84 32 56 77 6 79 90 122 7 12 122 108 57 33 71 105 11 21 109 63 2 79 114 29 51 102 115 110 109 33 106 61 122 24 25 53 8 96 86 49 15 90 81 120 22 52 40 39 71 107 34 9 64 20 100 115 27 6 42 56 98 77 23 74 28 98 71 50 15 70 75 221 16 74 39 117 111 91 100 64 99 18 43 76 121 17 38 105 91 92 52 117 69 96 72 61 77 121 84 7 6 112 97 115 63 112 98 2 86 195 118 47 52 121 75 99 18 79 25 127 10 35 121 89 108 101 11 40 74 5 62 81 65 104 111 121 [出力例] 884175 [入力例] 500 16285 13619 21183 21387 5008 17859 1156 3979 11678 20593 13590 10077 9381 21353 21672 9870 7211 896 12621 17778 15867 15297 21792 12378 118 9215 17872 12318 18773 17838 3565 8979 10067 18578 8079 13778 17207 7897 17187 15553 7630 13517 7931 1917 11753 12577 1152 17281 2188 3508 7666 15183 9121 367 10872 7191 11916 18617 21869 8653 3127 17019 20172 11297 2058 968 20723 16899 21370 12676 7137 7296 21557 20577 11276 17760 7777 17375 12367 1652 15593 18375 1680 7358 17785 17915 10036 18997 9789 7902 17965 19732 8920 7915 2029 21157 6783 11259 287 13737 11959 18892 15762 11273 19806 1076 13560 3959 8391 13301 10809 6897 6370 18215 7550 18523 20537 17659 1230 7210 9167 2573 9177 6278 7775 325 19779 16977 12077 8887 17965 3799 2976 20725 8737 18595 5983 20551 13107 9323 195 5038 20036 16508 6562 5767 10786 1298 18673 2610 7935 1975 7096 19635 13370 6358 6591 15879 15623 3318 12717 19289 7770 3357 9917 18706 1836 8532 13667 117 3077 6863 12358 17560 9755 5569 13995 20167 3660 9608 20772 22026 5301 9797 9912 17551 12372 7830 19150 6151 8655 18257 3523 8027 16531 8129 511 17517 7332 3967 18399 3000 673 595 7363 7662 17963 22155 21253 22052 13573 16723 7509 6630 13359 21376 20277 5658 17892 11766 18570 20877 13271 7858 6238 19327 7251 7570 2218 17780 3978 16857 9021 17317 19685 7387 5735 760 15507 230 19107 10939 17297 217 10079 15991 17500 7099 10292 6121 9376 5715 7688 3868 582 12671 11307 21157 5579 13317 5852 7857 17395 3008 17600 19790 20957 17869 17731 17678 16770 18259 20973 19185 5581 9577 8365 6782 2560 13785 10600 3687 3100 17756 10291 7328 15886 18703 11500 652 21839 17200 7016 7850 20179 13593 7983 36 11973 327 6099 17693 17572 6965 17173 12799 19212 12997 20768 775 8215 7531 9799 12973 3380 11732 6761 17099 6213 12970 17865 16291 20099 587 15802 11672 5171 12068 8871 3605 7860 17517 11606 850 15832 6060 18112 16997 1873 8571 5171 13957 5957 11656 13217 18768 16056 7173 17233 6502 20786 6320 11533 20197 17360 11877 12818 19906 10371 11500 17168 11777 3171 1787 13995 21803 10078 771 9860 10296 763 2702 8101 11817 18377 7168 16806 17813 17017 16717 17518 7851 13857 6659 726 7582 19919 8886 7087 19380 12071 19502 1178 15618 1986 16831 20566 15178 8387 3133 16867 10860 3832 17655 3999 16711 17970 21659 2265 979 19372 6067 695 12291 13502 17831 17602 8505 2763 18920 7789 20161 5027 17710 18785 11275 1326 16270 3067 6773 18812 6112 22127 2917 6897 20236 11867 7332 8572 18193 7059 11921 7050 6772 7913 13931 7839 19566 17177 17722 12167 19880 7998 9188 17171 21258 17778 16291 20831 21779 17817 5556 15612 8762 1838 12591 10375 17697 17627 8057 7900 20991 6778 9910 2038 8162 15851 5632 7067 10623 11977 7580 3016 18097 3535 2283 11093 16807 21797 19750 1161 525 8788 11278 1679 10878 20818 12762 12032 17105 [出力例] 5062588 |
■参照サイト
AtCoder Regular Contest 158