C++の練習を兼ねて, AtCoder Beginner Contest 287 の 問題C (Path Graph?) ~ 問題E (Karuta) を解いてみた.
■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 問題C で, 幅優先探索, 問題E で 再帰処理 の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 287 解説 の 各リンク を ご覧下さい.
■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 |
// 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, M; scanf("%d %d", &N, &M); vvi G(N); rep(i, M){ 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* 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[N], idx = 0; rep(i, N) c[i] = 0; rep(i, N) if(!c[i]) bfs(G, i, c, ++idx); // 3. 次数 1, 2 の 頂点 を 数える. int one = 0, two = 0; rep(i, N){ if(G[i].size() == 1) ++one; if(G[i].size() == 2) ++two; } // 4. 出力. printf("%s\n", (idx == 1 && one == 2 && two == (N - 2)) ? "Yes" : "No"); 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 |
[入力例] 4 3 1 3 4 2 3 2 [出力例] Yes ※AtCoderテストケースより [入力例] 2 0 [出力例] No ※AtCoderテストケースより [入力例] 5 5 1 2 2 3 3 4 4 5 5 1 [出力例] No ※AtCoderテストケースより [入力例] 5 4 1 2 2 3 3 4 4 5 [出力例] Yes [入力例] 7 6 3 2 2 1 1 7 7 6 6 5 5 4 [出力例] Yes [入力例] 5 4 1 2 5 3 3 4 4 5 [出力例] No |
■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 |
// 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 main(){ // 1. 入力情報. char s[303030], t[303030]; scanf("%s %s", s, t); string S(s), T(t); // 2. 一致するか? int ss = S.size(), ts = T.size(), l = 0, r = 0; rep(i, ts){ if(S[i] == T[i] || S[i] == '?' || T[i] == '?') ++l; else break; } repr(i, ss - 1, 0){ int j = i - (ss - ts); if(j >= 0 && S[i] == T[j] || S[i] == '?' || T[j] == '?') ++r; else break; } // 3. 出力. rep(x, ts + 1) printf("%s\n", ((x <= l) && (ts - x <= r)) ? "Yes" : "No"); 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 |
[入力例] a?c b? [出力例] Yes No No ※AtCoderテストケースより [入力例] atcoder ????? [出力例] Yes Yes Yes Yes Yes Yes ※AtCoderテストケースより [入力例] beginner contest [出力例] No No No No No No No No ※AtCoderテストケースより [入力例] aaaaa aaa [出力例] Yes Yes Yes Yes [入力例] gr?en?pp?e gapple [出力例] No Yes No No No No No [入力例] ?trawberry berry [出力例] Yes Yes No No No No [入力例] onep?usone??two ?ne?two [出力例] No No Yes Yes Yes Yes No No |
■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 |
// 解き直し. // https://atcoder.jp/contests/abc287/editorial/5609 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vs = vector<string>; 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 all(x) x.begin(), x.end() int memo[505050]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vs v; rep(i, N){ string s; cin >> s; v.pb(s); } // 2. dfs. // https://ja.wikipedia.org/wiki/深さ優先探索 auto dfs = [&](auto&& self, vi& idxs, int k) -> void { // グループ分け. vvi g(26); for(auto &idx : idxs) g[v[idx][k] - 'a'].pb(idx); // max LCP 設定. rep(i, 26){ // グループサイズが, 1以下. int gs = g[i].size(); if(gs == 0) continue; if(gs == 1){ memo[g[i][0]] = k; continue; } // グループサイズが, 2以上. rep(j, gs) if(v[g[i][j]].size() == k + 1) memo[g[i][j]] = k + 1; } // 再帰処理. rep(i, 26){ vi ng; for(auto &idx : g[i]) if(memo[idx] == -1) ng.pb(idx); if(ng.size()) self(self, ng, k + 1); } }; rep(i, 505050) memo[i] = -1; vi idxs(N); iota(all(idxs), 0); dfs(dfs, idxs, 0); // 3. 出力. rep(i, N) printf("%d\n", memo[i]); 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 122 123 124 125 126 127 128 129 130 131 132 133 |
[入力例] 3 abc abb aac [出力例] 2 2 1 ※AtCoderテストケースより [入力例] 11 abracadabra bracadabra racadabra acadabra cadabra adabra dabra abra bra ra a [出力例] 4 3 2 1 0 1 0 4 3 2 1 ※AtCoderテストケースより [入力例] 12 pqr pq pqrs pqrst pqq pqrstu pqrr pqrss pqrst q qr qrs [出力例] 3 2 4 5 2 5 3 4 5 1 2 2 [入力例] 30 abccb bcbcac bccbcba bcbaaacc dcbaaccbc acabcababc abcbabaabcc cbabccbaaacb baccccbaccbba cabcbcccaccbbb aaaaabaccaaabab ebacbcaaccaaccba bccbbaaaacbcaacab bbbaaccbcbbbbcaccc aabaabccbccbcbcaaba abcabcabcabcacaabbca aabbbacbbaabcaaabac faaaaacacbaaabcbbc bbbbabcccccbaaccc abcabcabccaaabca bbccccaccabcbaa abcabcaabcbbcc caacbbabccbca abcabcabcabc gacabcacbba bcccacbccaac abccbcbcabaac cbbaacbaccccca baccabaacababbb cbaacbacaaabbcbb [出力例] 5 3 4 3 0 1 3 3 4 2 2 0 4 3 3 12 3 0 3 9 2 7 2 12 0 3 5 2 4 3 |
■参照サイト
ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287)