C++の練習を兼ねて, AtCoder Beginner Contest 277 の 問題C (Ladder Takahashi) ～ 問題D (Takahashi’s Solitaire) を解いてみた.
■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達出来たと思う.
2. 個人的には, 問題C, D で, 幅優先探索 の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 277 解説 の 各リンク を ご覧下さい.
■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 |
// 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 #define a first #define b second int a[202020], b[202020], o[404040]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<int, int> m; m[1] = 0; rep(i, N){ scanf("%d %d", &a[i], &b[i]); m[a[i]] = 0; m[b[i]] = 0; } // 2. 座標圧縮. int idx = -1; for(auto &p : m) p.b = ++idx; for(auto &p : m) o[p.b] = p.a; // 3. グラフ作成. vvi G(idx + 1); rep(i, N){ G[m[a[i]]].pb(m[b[i]]); G[m[b[i]]].pb(m[a[i]]); } // 4. 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[idx + 1]; rep(i, idx + 1) d[i] = 0; bfs(G, 0, d); // 5. 最高で何階へ上れるか？ int ans = 1; rep(i, idx + 1) if(d[i]) ans = max(ans, o[i]); // 6. 出力. 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 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 |
[入力例] 4 1 4 4 3 4 10 8 3 [出力例] 10 ※AtCoderテストケースより [入力例] 6 1 3 1 5 1 12 3 5 3 12 5 12 [出力例] 12 ※AtCoderテストケースより [入力例] 3 500000000 600000000 600000000 700000000 700000000 800000000 [出力例] 1 ※AtCoderテストケースより [入力例] 5 1 3 1 5 2 3 4 5 2 7 [出力例] 7 [入力例] 20 187 89 159 225 26 1 27 177 124 151 206 333 29 26 89 29 191 74 156 42 62 45 1 27 53 30 42 4 1 10 175 111 10 22 113 174 206 22 20 171 [出力例] 333 |
■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 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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; 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 #define a first #define b second int a[202020]; LL t[202020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); LL ans = 0; map<int, int> m; rep(i, N){ scanf("%d", &a[i]); ans += (LL)a[i]; m[a[i]] = 0; } // 2. 座標圧縮. int idx = -1; for(auto &p : m) p.b = ++idx; vi v; for(auto &p : m) v.pb(p.a); v.pb(v.front()); // 3. 各整数の合計. for(auto &p : m) t[p.b] += (LL)p.a; // 4. グラフ作成. vvi G(idx + 1); rep(i, v.size() - 1){ if((v[i] + 1) % M == v[i + 1]){ G[m[v[i + 0]]].pb(m[v[i + 1]]); G[m[v[i + 1]]].pb(m[v[i + 0]]); } } // 5. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vvi &G, int s, int* c, int l){ // 空のキュー. queue<int> q; // 連結成分番号を設定. c[s] = l; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 取り出した要素を処理. for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e); } }; int c[idx + 1], n = 0; rep(i, idx + 1) c[i] = 0; rep(i, idx + 1) if(!c[i]) bfs(G, i, c, ++n); // 6. 連結成分ごとに集計. LL g[n + 1]; rep(i, n + 1) g[i] = 0; rep(i, N) g[c[m[a[i]]]] += t[m[a[i]]]; // 7. 最大値は？ LL gMax = 0; rep(i, n + 1) gMax = max(gMax , g[i]); // 8. 出力. printf("%lld\n", ans - gMax); 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 |
[入力例] 9 7 3 0 2 5 5 3 0 6 3 [出力例] 11 ※AtCoderテストケースより [入力例] 1 10 4 [出力例] 0 ※AtCoderテストケースより [入力例] 20 20 18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12 [出力例] 99 ※AtCoderテストケースより [入力例] 50 123 80 110 3 22 46 88 40 64 40 91 32 60 109 73 43 68 23 118 55 59 67 83 83 37 5 89 24 45 34 21 37 61 72 7 119 36 105 26 114 3 49 37 86 113 115 79 122 25 5 76 [出力例] 2657 [入力例] 100 1234 215 1020 246 682 852 664 1057 811 639 129 40 929 845 948 485 1174 47 1048 1150 827 929 1204 704 959 1101 169 430 1073 96 621 519 1173 1107 654 320 1105 292 684 854 386 866 189 460 994 504 748 1162 461 778 496 271 1179 1190 612 423 791 310 614 307 849 160 433 506 449 326 399 247 581 1195 1108 1013 664 1187 36 1211 334 633 97 1188 1009 1018 770 638 351 1090 1165 1050 614 1119 788 187 1187 246 1022 64 1224 957 17 406 1111 [出力例] 65630 [入力例] 200 123 12 18 6 72 23 90 66 25 12 34 43 104 114 56 89 116 21 38 30 50 24 46 80 94 88 87 35 50 84 31 100 20 3 29 87 23 79 94 3 30 37 42 21 30 33 88 114 69 84 18 17 100 22 69 70 18 109 115 86 30 64 7 97 111 85 81 3 29 14 117 103 55 75 30 118 104 57 35 108 20 87 50 104 28 24 39 18 68 26 97 69 100 19 94 6 37 111 9 46 60 2 72 56 6 13 58 109 63 28 47 62 81 90 90 82 48 92 118 116 81 82 45 100 65 8 122 22 53 23 119 6 86 33 96 35 93 119 0 63 50 10 8 109 104 84 16 73 115 29 19 3 86 99 106 1 86 60 100 57 5 28 64 27 111 6 67 91 77 71 14 118 21 84 39 91 10 94 113 22 5 12 51 55 16 1 102 24 18 104 122 103 79 65 77 61 13 91 90 0 50 [出力例] 9189 |
■参照サイト
大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)