C++の練習を兼ねて, AtCoder Beginner Contest 328 の 問題C (Consecutive) ～ 問題E (Modulo MST) を解いてみた.
■感想.
1. 問題C ～ E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題E で, 幅優先探索 の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 328 解説 の 各リンク を ご覧下さい.
■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 |
// C++20(GCC 12.2) #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 pCum[303030]; int main(){ // 1. 入力情報. int N, Q; char c[303030]; scanf("%d %d %s", &N, &Q, c); string S(c); S = '#' + S; // 2. 累積和. rep(i, N) pCum[i + 1] = pCum[i] + (S[i] == S[i + 1]); // 3. クエリ回答. rep(i, Q){ int l, r; scanf("%d %d", &l, &r); printf("%d\n", pCum[r] - pCum[l]); } 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 |
[入力例] 11 4 mississippi 3 9 4 10 4 6 7 7 [出力例] 2 2 0 0 ※AtCoderテストケースより [入力例] 5 1 aaaaa 1 5 [出力例] 4 ※AtCoderテストケースより [入力例] 15 7 xxxxyyyyyzzzzzz 1 3 3 3 2 5 4 8 7 11 12 13 1 15 [出力例] 2 0 2 3 3 1 12 |
■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 |
// C++20(GCC 12.2) #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--) #define pb push_back #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. char c[202020]; scanf("%s", c); string S(c); int ss = S.size(); // 2. "ABC" を 削除. stack<char> st; rep(i, ss){ // 2文字未満 or 'C'以外. if(st.size() < 2 || S[i] != 'C'){ st.push(S[i]); continue; } // "AB" が 出現済か？ char c1 = st.top(); st.pop(); char c2 = st.top(); st.pop(); if(c2 == 'A' && c1 == 'B') continue; // 戻し & 追加. st.push(c2); st.push(c1); st.push(S[i]); } // 3. 最終的な S は？ string ans; while(!st.empty()){ ans.pb(st.top()); st.pop(); } reverse(all(ans)); // 4. 出力. printf("%s\n", ans.c_str()); 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 |
[入力例] BAABCBCCABCAC [出力例] BCAC ※AtCoderテストケースより [入力例] ABCABC [出力例] ※AtCoderテストケースより [入力例] AAABCABCABCAABCABCBBBAABCBCCCAAABCBCBCC [出力例] AAABBBCCC ※AtCoderテストケースより [入力例] BBBAABACABCACCBCBCBAACBCCACAABCCCBABCABBAACACCBABC [出力例] BBBAABACACCBCBCBAACBCCACACCBABBAACACCB [入力例] ABCACABBABCBBABACAABCCCBAABACBABABCACBAABACABCACAAABCCBBCBAACCACCBACCAABCCABCCCABCCCCBBABBCAACABCABC [出力例] ACABBBBABACACCBAABACBABACBAABACACAACBBCBAACCACCBACCACCCCCCBBABBCAAC |
■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 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 |
// C++20(GCC 12.2) #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 const int INF = 2020202020; int u[33], v[33]; LL w[33]; int main(){ // 1. 入力情報. int N, M; LL K; scanf("%d %d %lld", &N, &M, &K); rep(i, M){ scanf("%d %d %lld", &u[i], &v[i], &w[i]); --u[i]; --v[i]; } // 2. 全域木 T の 辺候補は？ vi es; rep(i, 1 << M) if(__builtin_popcount(i) == N - 1) es.pb(i); // for(auto &e : es) printf("%d\n", e); // 3. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vvi &G, int s, int* d){ // 空のキュー. queue<int> q; // 探索開始地点 s をキューに追加. q.push(s); // 探索開始地点 s は, 距離ゼロ. d[s] = 0; // キューを処理. while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 取り出した要素を処理. for(auto &v : G[u]) if(d[v] == INF && v != s) d[v] = d[u] + 1, q.push(v); } }; // 4. 全域木のコストの最小値は？ LL ans = 202020202020202020; for(auto &e : es){ // グラフ構築 & コスト集計. vvi G(N); LL cost = 0; rep(i, M){ if((1 << i) & e){ G[u[i]].pb(v[i]); G[v[i]].pb(u[i]); cost += w[i]; cost %= K; } } // グラフは, 木か？ int d[N]; rep(i, N) d[i] = INF; bfs(G, 0, d); bool ok = true; rep(i, N) if(d[i] == INF) ok = false; if(!ok) continue; // 最小値更新. // printf("%d %lld\n", e, cost); ans = min(ans, cost); } // 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 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 |
[入力例] 5 6 328 1 2 99 1 3 102 2 3 86 2 4 94 2 5 95 3 4 81 [出力例] 33 ※AtCoderテストケースより [入力例] 6 5 998244353 1 2 337361568 1 6 450343304 2 3 61477244 2 5 745383438 4 5 727360840 [出力例] 325437688 ※AtCoderテストケースより [入力例] 8 28 936294041850197 1 2 473294720906780 1 3 743030800139244 1 4 709363019414774 1 5 383643612490312 1 6 557102781022861 1 7 623179288538138 1 8 739618599410809 2 3 857687812294404 2 4 893923168139714 2 5 581822471860662 2 6 740549363586558 2 7 307226438833222 2 8 447399029952998 3 4 636318083622768 3 5 44548707643622 3 6 307262781240755 3 7 12070267388230 3 8 700247263184082 4 5 560567890325333 4 6 704726113717147 4 7 588263818615687 4 8 549007536393172 5 6 779230871080408 5 7 825982583786498 5 8 713928998174272 6 7 751331074538826 6 8 449873635430228 7 8 11298381761479 [出力例] 11360716373 ※AtCoderテストケースより [入力例] 4 6 100 1 2 543 1 3 123 1 4 321 2 3 555 2 4 111 3 4 222 [出力例] 0 ※実際, 辺 2, 4, 6 を 選択した場合, (123 + 555 + 222) % 100 = 0 となる [入力例] 5 7 1234 1 2 86587 2 3 77532 3 4 84661 4 5 52062 1 5 63206 1 4 72092 3 5 82403 [出力例] 21 ※実際, 辺 2, 4, 5, 7 を 選択した場合, (77532 + 52062 + 63206 + 82403) % 1234 = 21 となる [入力例] 6 10 20231123 1 2 84117461 1 6 55841423 2 3 72564375 2 4 21686910 2 5 22158045 2 6 42781720 3 4 14540220 3 5 89483069 3 6 90561012 5 6 98083075 [出力例] 20000 ※実際, 辺 1, 3, 6, 7, 8 を 選択した場合, (84117461 + 72564375 + 42781720 + 14540220 + 89483069) % 20231123 = 20000 となる |
■参照サイト
トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)