C++の練習を兼ねて, AtCoder Beginner Contest 221 の 問題C (Select Mul) ~ 問題D (Online games) を解いてみた.
■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達できたと思う.
2. いもす法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 221 解説 の 各リンク を ご覧下さい.
■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 |
// 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 #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. char x[22]; scanf("%s", x); string N(x); // 2. 分離後の二数の積を全探索. int ans = 0, n = N.size(); vi z(n); iota(all(z), 0); do{ rep(i, n / 2){ // 二数に分離. string s1 = ""; string s2 = ""; rep(j, i + 1) s1.pb(N[z[j]]); repx(j, i + 1, n) s2.pb(N[z[j]]); // 先頭が, '0' か? if(s1[0] == '0' || s2[0] == '0') continue; // 二数の積. int n1 = stoi(s1); int n2 = stoi(s2); // 最大値更新. ans = max(ans, n1 * n2); } }while(next_permutation(all(z))); // 3. 出力. 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 |
[入力例] 123 [出力例] 63 ※AtCoderテストケースより [入力例] 1010 [出力例] 100 ※AtCoderテストケースより [入力例] 998244353 [出力例] 939337176 ※AtCoderテストケースより [入力例] 2021 [出力例] 420 [入力例] 314159265 [出力例] 623527551 [入力例] 173205080 [出力例] 624912000 |
■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 |
// 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--) #define a first #define b second LL a[202020], b[202020], ans[202020]; int c[404040]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<LL, int> im; map<int, LL> om; rep(i, N){ scanf("%lld %lld", &a[i], &b[i]); im[a[i]] = 0; im[a[i] + b[i]] = 0; } // 2. 番号付け. int idx = -1; for(auto &p : im) p.b = ++idx, om[idx] = p.a; // 3. いもす法. rep(i, N){ int l = im[a[i]]; int r = im[a[i] + b[i]]; c[l]++; c[r]--; } rep(i, 400000) c[i + 1] += c[i]; // 4. k人がログインしていた日数. rep(i, 400000) ans[c[i]] += om[i + 1] - om[i]; // 5. 出力. repx(i, 1, N + 1){ printf("%lld", ans[i]); printf("%s", (i < N) ? " " : "\n"); } 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 |
[入力例] 3 1 2 2 3 3 1 [出力例] 2 2 0 ※AtCoderテストケースより [入力例] 2 1000000000 1000000000 1000000000 1000000000 [出力例] 0 1000000000 ※AtCoderテストケースより [入力例] 10 29 113 29 21 100 52 15 58 85 89 38 72 44 7 12 42 30 87 72 114 [出力例] 15 36 10 56 34 17 6 0 0 0 [入力例] 25 8642 9550 3534 5649 3177 4693 898 7837 3207 7538 11877 7261 6821 6304 8743 213 5200 10755 4530 10628 7694 1049 8492 9985 3108 9020 6921 10630 7481 4095 493 4566 8699 5737 2279 7706 6404 7709 11787 5039 8220 9497 7817 851 10152 5571 10144 7799 5539 2309 [出力例] 1066 1666 1078 295 196 1052 2008 1100 1430 1139 423 1918 3291 1488 433 62 0 0 0 0 0 0 0 0 0 [入力例] 50 106993193 110506795 52775875 93411737 58018201 76224909 10744043 8169294 65389174 25786656 85246147 96407126 8357758 83421294 47672496 62059620 85986379 39563845 62913817 107693619 47410286 99119327 117431975 36082668 99982039 80945023 53858763 119274201 63989315 87845094 15977620 14635186 26635628 107530968 96859987 18732383 50253111 49618390 99750465 122485976 23644033 51034554 14851679 36874388 15653638 55430517 78536425 115668447 207787 116135293 91217773 22887742 70638978 116239554 77819066 116028254 110968843 64273162 37752441 14081788 26432536 1833150 59889650 99660574 87080799 56031237 115222597 69051605 85844657 37146399 41362872 9604546 65235927 78184476 83556947 116427610 60575320 91698260 104769068 64143291 93331849 24615529 100866735 67411609 69168973 92662727 118036814 43409596 46570811 44040167 66152426 69582203 106945431 70741959 102770017 15526819 78050972 52740724 11939312 8779499 [出力例] 12886424 19901716 6974954 3269919 10695969 14661924 11717289 7564208 5020793 3898645 9607743 5111284 2380747 2972512 7522142 1631902 2049433 6798833 7398089 5735514 6235426 5362523 4456409 906877 9113869 7240208 6607709 4380632 7144754 4558219 8048914 3927706 6245368 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
■参照サイト
AtCoder Beginner Contest 221