C++の練習を兼ねて, AtCoder Regular Contest 139 の 問題A (Trailing Zeros) ~ 問題B (Make N) を解いてみた.
■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 139 解説 の 各リンク を ご覧下さい.
■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 44 45 46 47 48 49 |
// 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 cPow2[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ int t; scanf("%d", &t); cPow2[i] = (1LL << t); } // 2. 数列 A を 構成. LL ans = cPow2[0]; repx(i, 1, N){ // 前回分結果を参照. LL q = ans / cPow2[i]; LL r = ans % cPow2[i]; // 余りがある. if(r) ++q; // 今回分候補. LL s = q * cPow2[i]; // 大小比較. if(s <= ans) s += cPow2[i]; // bit調整. if(!(s & cPow2[i])) s += cPow2[i]; // 今回分更新. ans = s; } // 3. 出力. 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 |
[入力例] 4 0 1 3 2 [出力例] 12 ※AtCoderのテストケースより [入力例] 5 4 3 2 1 0 [出力例] 31 ※AtCoderのテストケースより [入力例] 1 40 [出力例] 1099511627776 ※AtCoderのテストケースより [入力例] 8 2 0 2 2 0 4 2 4 [出力例] 80 ※AtCoderのテストケースより [入力例] 12 2 0 2 2 0 6 0 8 2 3 5 9 [出力例] 512 [入力例] 50 23 4 17 9 10 23 15 22 19 9 20 22 24 12 1 14 4 14 17 21 17 20 11 15 15 2 2 14 16 18 0 5 1 18 22 5 14 5 20 8 13 21 8 20 0 6 13 24 24 10 [出力例] 117441536 [入力例] 100 0 7 2 36 22 14 3 7 5 5 13 35 6 0 27 34 28 12 33 33 0 32 36 1 4 18 19 20 29 7 23 32 19 38 37 24 36 6 4 9 0 10 29 36 11 32 39 2 0 17 22 24 15 0 23 32 1 15 31 0 6 38 6 18 16 5 8 9 7 15 12 9 8 34 31 36 5 7 39 11 10 21 8 5 28 30 14 25 31 39 0 27 4 3 28 30 29 24 2 5 [出力例] 3849918087200 |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc139/editorial/3836 // 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){ // 操作情報. LL N, A, B, X, Y, Z; scanf("%lld %lld %lld %lld %lld %lld", &N, &A, &B, &X, &Y, &Z); // swap. if(Y * B > A * Z){ swap(A, B); swap(Y, Z); } // コスト置き換え. Y = min(Y, A * X); Z = min(Z, B * X); // A で 全探索. LL ans = N * X; int u = sqrt(max({A, B, N, X, Y, Z})) + 1; rep(j, u + 1){ // Skip. if(A * j > N) break; // 1 増加 … k 回. // A 増加 … j 回. LL k = N - A * j; ans = min(ans, X * k + Y * j); } // B で 全探索. rep(j, u + 1){ // Skip. if(B * j > N) break; // 1 増加 … l 回. // A 増加 … k 回. // B 増加 … j 回. LL k = (N - B * j) / A; LL l = (N - B * j) % A; ans = min(ans, X * l + Y * k + Z * j); } // 出力. 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 |
[入力例] 5 10 3 5 2 3 6 10 3 5 1 1000000000 1000000000 139 2 139 1 1 1 139 1 1 1 1 1 139 7 10 3845 26982 30923 [出力例] 11 10 1 139 436604 ※AtCoderのテストケースより [入力例] 3 19 410 118 10 12 36 28 5 27 120 8 19 15 10 112 25 26 7 [出力例] 190 139 151 [入力例] 10 5 27 33 27 33 10 367 101 97 360 89 296 356 163 1670 2229 294 2104 22210 20463 1180 1423 7189 27349 96546 85717 99062 38671 64408 12833 428087 957323 524008 764193 831124 151120 2848490 8806972 3102003 4652749 7816487 1589401 2647523 1539654 6853977 1911564 2014335 9516618 417378 3673854 9480440 5925970 3262795 9490280 8960289 770367 364602 1730798 1749930 7559817 [出力例] 135 23307 67458 841379 418832667 327141088791 13253308999010 2117764511451 2473369506660 7082779836 [入力例] 20 6 20 87 64 34 7 82 8 17 96 34 9 308 143 331 229 216 156 407 125 205 150 333 367 3032 2513 2381 3514 3560 2087 3295 1839 1278 1709 2260 2581 3050 3254 4972 4036 6020 5585 5206 2806 5496 7172 3857 2522 5129 14571 10270 10633 7610 5848 8794 6857 14204 13178 5698 12289 23689 21296 23641 19172 23862 17712 26284 19956 21528 21533 26547 18181 47943 42530 37022 46535 46198 32736 30053 47292 34998 32635 30911 37386 214765 82103 226279 148757 72521 50203 115274 248505 25061 123613 174816 93462 748091 224818 872731 776979 327633 368494 885709 129641 646432 186800 1006696 172215 1247487 1840364 1971807 2229106 1738446 1319308 1871210 2216170 1482305 2121565 2133141 1368115 [出力例] 384 222 5470 5799 1827326 309043 12309800 17216657 54536657 25531484 937968 102429129 251940153 980779655 7521150205 1858277238 57215385522 20154848576 2780780756622 825088604440 |
■参照サイト
AtCoder Regular Contest 139