C++の練習を兼ねて, AtCoder Beginner Contest 270 の 問題C (Simple path) ～ 問題E (Apple Baskets on Circle) を解いてみた.
■感想.
1. 問題Dは, 想定誤解法から抜け出せなかったので, 解説を参考に, AC版に到達できたと思う.
2. 問題Dで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 問題C で, 幅優先探索, 問題E で, 二分探索の 復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 270 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #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 main(){ // 1. 入力情報. int N, X, Y; scanf("%d %d %d", &N, &X, &Y); --X, --Y; vvi G(N); rep(i, N - 1){ int u, v; scanf("%d %d", &u, &v); --u, --v; G[u].pb(v); G[v].pb(u); } // 2. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vvi &G, int s, int* d){ // 空のキュー. queue<int> q; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 隣接頂点をチェック. for(auto &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v); } }; int d[N]; rep(i, N) d[i] = 0; bfs(G, X, d); // 3. 最短経路. auto f = [&](vvi &G, int s, int* d, vi& r){ // 空のキュー. queue<int> q; // 探索地点 s をキュー q に追加. q.push(s); r.pb(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 取り出した要素を処理. for(auto &v : G[u]){ // 距離 が 1 小さい場合に, 保存. if(d[v] == d[u] - 1){ r.pb(v); q.push(v); break; } } } }; vi ans; f(G, Y, d, ans); // 4. 出力. int n = ans.size(); repr(i, n - 1, 0) printf("%d%s", ans[i] + 1, i ? " " : "\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 |
[入力例] 5 2 5 1 2 1 3 3 4 3 5 [出力例] 2 1 3 5 ※AtCoderテストケースより [入力例] 6 1 2 3 1 2 5 1 2 4 1 2 6 [出力例] 1 2 ※AtCoderテストケースより [入力例] 7 5 3 1 2 7 2 7 6 7 5 3 6 6 4 [出力例] 5 7 6 3 [入力例] 15 12 5 11 10 11 8 10 13 14 10 15 14 12 14 8 7 8 6 6 1 6 5 1 2 1 9 9 3 9 4 [出力例] 12 14 10 11 8 6 5 [入力例] 20 10 18 5 4 6 4 4 7 7 8 8 9 8 19 8 20 19 1 19 2 19 3 1 10 20 11 20 13 20 14 13 12 13 15 13 16 13 17 13 18 [出力例] 10 1 19 8 20 13 18 |
■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 |
// 解き直し. // https://atcoder.jp/contests/abc270/editorial/4850 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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 a[101], dp[10101]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); rep(i, K) scanf("%d", &a[i]); // 2. ゲーム. rep(i, N + 1) rep(j, K + 1) if(i - a[j] >= 0) dp[i] = max(dp[i], a[j] + (i - a[j]) - dp[i - a[j]]); // 3. 出力. printf("%d\n", dp[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 |
[入力例] 10 2 1 4 [出力例] 5 ※AtCoderテストケースより [入力例] 11 4 1 2 3 6 [出力例] 8 ※AtCoderテストケースより [入力例] 10000 10 1 2 4 8 16 32 64 128 256 512 [出力例] 5136 ※AtCoderテストケースより [入力例] 2022 15 1 3 10 11 16 18 20 21 24 27 30 33 39 43 51 [出力例] 1020 [入力例] 10000 25 1 4 6 11 17 25 30 36 39 41 50 53 55 60 63 70 76 81 87 88 91 93 98 103 111 [出力例] 5005 |
■C++版プログラム(問題E／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 |
// 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]; int main(){ // 1. 入力情報. int N; LL K; scanf("%d %lld", &N, &K); rep(i, N) scanf("%lld", &a[i]); // 2. 評価関数. auto f = [&](LL m) -> bool { // 2-1. りんごを, 最大 m 個ずつ食べた. LL cur = 0; rep(i, N) cur += min(a[i], m); // 2-2. 判定結果. return (cur <= K); }; // 3. 二分探索で確認してみる. LL l = -1, h = 2e12 + 1, m; while(l + 1 < h){ LL m = (h + l) >> 1; if(f(m)) l = m; else h = m; } // 4. l 周後は？ rep(i, N){ K -= min(a[i], l); a[i] -= min(a[i], l); } // 5. まだりんごが食べられる場合. rep(i, N){ if(K == 0) break; K -= min(a[i], 1LL); a[i] -= min(a[i], 1LL); } // 6. 出力. rep(i, N) printf("%lld%s", a[i], (i < N - 1) ? " " : "\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 |
[入力例] 3 3 1 3 0 [出力例] 0 1 0 ※AtCoderテストケースより [入力例] 2 1000000000000 1000000000000 1000000000000 [出力例] 500000000000 500000000000 ※AtCoderテストケースより [入力例] 10 21 3 1 4 1 5 9 2 6 5 3 [出力例] 0 0 1 0 2 7 0 4 3 1 [入力例] 30 2022 92 128 58 79 83 54 88 66 98 84 116 53 103 70 53 72 82 121 97 61 107 51 115 56 71 87 90 105 12 92 [出力例] 17 53 0 4 8 0 13 0 23 9 41 0 28 0 0 0 7 46 22 0 32 0 41 0 0 13 16 31 0 18 [入力例] 300 20220925 84179 62870 97544 31943 77523 34777 100072 33029 79036 95524 104597 50581 69487 97904 68416 93643 49670 54396 94721 82777 78561 108339 94265 88431 49009 84955 60155 53688 36556 109031 44070 32236 76699 49332 101983 33841 36540 42339 69883 45574 54482 109013 33569 62492 32785 70787 56746 97920 94729 56586 65349 68738 35679 37124 53041 108899 37692 70719 34887 34074 32904 100389 47716 95627 52623 103358 99094 80182 103888 105515 54187 79559 65358 82494 32233 42767 65003 64016 42905 86831 87898 103926 75099 36521 42039 32751 47762 101831 79229 61616 94328 69907 96916 69666 35182 51593 107696 56703 42137 95111 60545 51030 86882 65570 51921 95783 39520 105441 67277 49068 38458 96961 41332 106481 102715 68835 108373 51080 94093 30166 90688 104360 67362 77686 102744 75310 74611 43536 93262 73873 34016 36757 40946 66899 89744 53575 39890 98110 99970 52393 69725 44696 92764 84847 67233 75814 93908 48517 100135 40835 77002 48630 42000 45642 68531 85979 68151 34428 57676 95055 67407 33687 72138 65996 60389 59174 106243 87415 72825 78073 63304 95889 99888 64730 59475 53716 73804 76717 30441 102873 69961 63113 92081 88353 45839 86385 72020 88993 64178 103156 49831 79480 105906 32582 38832 39724 77070 81396 61516 94600 86791 61350 50591 87229 37942 83047 34594 109389 71897 107547 71122 49263 107606 53922 42278 50771 35411 64597 31771 108308 35561 56434 41777 59937 104314 87334 84610 41387 72072 63971 53982 53348 83283 95228 102347 69586 67197 107944 91309 70085 69264 76873 100509 74832 79701 78740 72639 70859 75665 36443 103241 106616 55615 48652 75884 96568 35732 43139 65420 107881 33255 101503 83393 45436 48280 80391 79787 94859 94050 48323 33802 52520 32577 74861 51716 107031 94177 60988 35108 30149 34713 58798 56565 82377 42850 33105 76773 60219 73108 35524 65150 48358 37679 97556 60253 43450 64260 52765 70123 58630 [出力例] 0 0 192 0 0 0 2720 0 0 0 7245 0 0 552 0 0 0 0 0 0 0 10987 0 0 0 0 0 0 0 11679 0 0 0 0 4631 0 0 0 0 0 0 11661 0 0 0 0 0 568 0 0 0 0 0 0 0 11547 0 0 0 0 0 3037 0 0 0 6006 1742 0 6536 8163 0 0 0 0 0 0 0 0 0 0 0 6574 0 0 0 0 0 4479 0 0 0 0 0 0 0 0 10344 0 0 0 0 0 0 0 0 0 0 8089 0 0 0 0 0 9129 5364 0 11022 0 0 0 0 7009 0 0 5393 0 0 0 0 0 0 0 0 0 0 0 0 759 2619 0 0 0 0 0 0 0 0 0 2784 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8892 0 0 0 0 0 2537 0 0 0 0 0 0 5522 0 0 0 0 0 0 0 0 0 5805 0 0 8555 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12038 0 10196 0 0 10255 0 0 0 0 0 0 10957 0 0 0 0 6963 0 0 0 0 0 0 0 0 0 4996 0 0 10593 0 0 0 0 3158 0 0 0 0 0 0 0 5890 9265 0 0 0 0 0 0 0 10530 0 4152 0 0 0 0 0 0 0 0 0 0 0 0 0 9680 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 205 0 0 0 0 0 0 |