C++の練習を兼ねて, AtCoder Beginner Contest 321 の 問題C (321-like Searcher) ～ 問題D (Set Menu) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題C で, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 321 解説 の 各リンク を ご覧下さい.
■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 |
// C++20(GCC 12.2) #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 K; scanf("%d", &K); // 2. dfs. // https://ja.wikipedia.org/wiki/深さ優先探索 set<LL> st; auto dfs = [&](auto&& self, LL d){ // 2-1. 保存. st.insert(d); // 2-2. 終了条件. int r = d % 10; if(r == 0) return; // 2-3. 追加(1 の 位). rep(i, r) self(self, 10 * d + i); }; // 3. 321-like Number 生成(1022個). repx(i, 1, 10) dfs(dfs, i); // printf("st.size()=%d\n", st.size()); // 4. K 番目は？ LL ans = 0; for(auto &x : st){ ans = x; if(--K == 0) break; } // 5. 出力. 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 |
[入力例] 15 [出力例] 32 ※AtCoderテストケースより [入力例] 321 [出力例] 9610 ※AtCoderテストケースより [入力例] 777 [出力例] 983210 ※AtCoderテストケースより [入力例] 20 [出力例] 50 [入力例] 100 [出力例] 750 [入力例] 753 [出力例] 975421 [入力例] 1022 [出力例] 9876543210 |
■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 |
// C++20(GCC 12.2) #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 all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N, M, P; scanf("%d %d %d", &N, &M, &P); vl a(N), b(M); rep(i, N) scanf("%lld", &a[i]); rep(i, M) scanf("%lld", &b[i]); // 2. sort. sort(all(a)); sort(all(b)); // 3. 累積和. vl bCum(M + 1, 0); rep(i, M) bCum[i + 1] = bCum[i] + b[i]; // 4. 定食の価格の総和. LL ans = 0; rep(i, N){ int at = lower_bound(all(b), P - a[i]) - b.begin(); ans += bCum[at] + a[i] * at; ans += (LL)P * (LL)(M - at); } // 5. 出力. 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 |
[入力例] 2 2 7 3 5 6 1 [出力例] 24 ※AtCoderテストケースより [入力例] 1 3 2 1 1 1 1 [出力例] 6 ※AtCoderテストケースより [入力例] 7 12 25514963 2436426 24979445 61648772 23690081 33933447 76190629 62703497 11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857 [出力例] 2115597124 ※AtCoderテストケースより [入力例] 5 3 123 1 2 3 4 5 6 7 8 [出力例] 150 [入力例] 5 3 10 11 12 13 14 15 16 17 18 [出力例] 150 [入力例] 12 15 100000 64871 99252 11934 88203 110776 8275 1116 81869 16238 6552 17514 71649 47327 17873 111561 24780 17782 18870 51552 44546 113673 91382 32723 10999 103361 53973 64043 [出力例] 14227081 [入力例] 30 50 2500 2453 1367 2387 1093 613 1649 1990 910 101 913 1745 1644 2016 1796 1518 2112 2492 1139 2145 703 2225 959 2408 691 1529 864 821 951 2030 2364 1319 857 921 1939 2203 1884 1799 565 2018 1595 12 1638 996 1197 740 1038 2449 1073 1580 2449 1871 870 111 1576 2410 769 1711 2475 1634 2354 1884 1919 943 446 385 803 1618 348 358 1904 2045 2310 1782 1419 1126 1067 1535 64 2161 121 [出力例] 3402202 [入力例] 100 120 33333 14021 11206 4523 11383 704 21471 18313 12778 19149 10164 17165 10474 9934 2338 7657 12326 24422 6017 7482 7051 11148 13353 9444 16507 22077 21448 71255 20038 11640 17509 20149 7140 11280 327 22036 7580 8152 8686 15626 2617 21718 24964 9124 2813 13294 7855 24045 33238 13222 17043 13099 13126 18103 11068 22719 18441 1408 3640 7297 17074 4026 19471 20520 16667 10446 10834 12555 23445 1400 9644 24859 5472 222 23622 5946 23745 1440 1177 11130 8323 6627 24306 2669 229 18585 22270 5108 3641 4965 7130 11704 12396 19223 20115 17845 15612 10896 28 16299 12696 5280 16707 19516 17340 17379 56449 5037 11102 13189 13580 21477 22974 4607 17792 23474 23608 13913 18909 16060 3294 24606 6395 10719 10251 5608 22507 468 14804 8974 1357 4676 2748 111 18762 22817 9519 22569 14121 2198 13482 8642 4809 12622 23327 21821 6910 7153 19971 88783 4436 2067 20006 24267 9989 12288 2916 897 13812 205 14842 3604 6621 13595 932 11239 2238 176 20816 52247 12707 12895 71897 23032 8565 158 11641 21871 15146 6251 14621 2671 19909 21476 15272 5099 18902 16681 12731 3174 3155 4544 11628 23976 18968 3208 4721 24082 13040 4900 5015 5437 133 23114 20152 24286 8952 7540 11692 19253 20774 22949 20821 21565 3656 12576 6234 2845 1739 6693 728 [出力例] 282120162 |