C++の練習を兼ねて, AtCoder Beginner Contest 293 の 問題C (Make Takahashi Happy) ～ 問題D (Tying Rope) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. Union-Find木 の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 293 解説 の 各リンク を ご覧下さい.
■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 |
// 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[11][11]; int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); rep(i, H) rep(j, W) scanf("%d", &a[i][j]); // 2. 数え上げ. int ans = 0, n = 1 << (H + W - 2); rep(i, n){ // 経路でない. if(__builtin_popcount(i) != H - 1) continue; // 初期化. int h = 0, w = 0; set<int> st; st.insert(a[0][0]); st.insert(a[H - 1][W - 1]); // 経路である. rep(j, H + W - 2){ // 下. if(i & (1 << (H + W - 3 - j))){ ++h; st.insert(a[h][w]); continue; } // 右. ++w; st.insert(a[h][w]); } // 嬉しくなるか？ if(st.size() == H + W - 1) ++ans; } // 3. 出力. 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 |
[入力例] 3 3 3 2 2 2 1 3 1 5 4 [出力例] 3 ※AtCoderテストケースより [入力例] 10 10 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 [出力例] 48620 ※AtCoderテストケースより [入力例] 5 5 8 3 5 11 3 5 11 10 6 12 12 6 5 7 11 1 4 1 9 10 12 10 7 8 12 [出力例] 5 [入力例] 10 7 24 27 11 4 30 11 32 30 23 14 3 13 16 23 5 17 4 3 27 21 14 18 27 8 27 23 10 25 16 20 10 20 1 2 28 20 5 18 9 29 12 22 4 1 30 30 14 19 27 7 10 17 13 31 28 22 1 2 21 18 24 10 29 28 14 15 14 13 26 23 [出力例] 37 [入力例] 10 10 99 65 21 86 51 90 5 82 79 59 43 57 32 94 57 86 39 39 16 100 57 21 77 61 61 36 88 48 99 90 36 46 55 5 32 32 83 80 78 45 26 40 91 16 94 39 40 61 6 41 15 61 74 3 17 7 10 25 52 79 88 12 31 33 96 21 86 50 71 92 12 66 23 5 36 23 59 57 72 16 57 61 65 16 55 76 77 56 94 20 56 32 48 37 82 56 60 29 33 93 [出力例] 3141 |
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #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--) // https://github.com/atcoder/live_library/blob/master/uf.cpp // UnionFind // coding: https://youtu.be/TdR816rqc3s?t=726 // comment: https://youtu.be/TdR816rqc3s?t=6822 // -> 一部改変. struct UnionFind{ vi d; UnionFind(int n = 0): d(n, -1) {} int find(int x){ return (d[x] < 0) ? x : (d[x] = find(d[x])); } bool unite(int x, int y){ x = find(x); y = find(y); if(x == y) return false; if(d[x] > d[y]) swap(x, y); d[x] += d[y]; d[y] = x; return true; } bool same(int x, int y){ return find(x) == find(y); } int size(int x){ return -d[find(x)]; } }; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); // 2. 初期化. UnionFind uf(2 * N + 4); rep(i, N) uf.unite(2 * i, 2 * i + 1); // 3. 操作. // -> ロープ P の R, B を 頂点 2 * P, 2 * P + 1 と 読み替える. int X = 0; rep(i, M){ // 操作情報. int a, c; char b[11], d[11]; scanf("%d %s %d %s", &a, b, &c, d); --a, --c; // 頂点は？ a = 2 * a + (b[0] == 'B'); c = 2 * c + (d[0] == 'B'); // 環状となった. if(uf.same(a, c)){ ++X; continue; } // ロープを繋げる. uf.unite(a, c); } // 4. 連結成分の個数. set<int> st; rep(i, N){ st.insert(uf.find(2 * i)); st.insert(uf.find(2 * i + 1)); } int Y = st.size() - X; // 5. 出力. printf("%d %d\n", X, Y); 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 |
[入力例] 5 3 3 R 5 B 5 R 3 B 4 R 2 B [出力例] 1 2 ※AtCoderテストケースより [入力例] 7 0 [出力例] 0 7 ※AtCoderテストケースより [入力例] 7 6 5 R 3 R 7 R 4 R 4 B 1 R 2 R 3 B 2 B 5 B 1 B 7 B [出力例] 2 1 ※AtCoderテストケースより [入力例] 5 2 1 R 2 B 2 R 1 B [出力例] 1 3 [入力例] 5 4 1 R 2 B 2 R 3 B 3 R 4 B 4 B 1 R [出力例] 1 1 [入力例] 10 8 1 R 2 B 2 R 3 B 3 R 1 B 5 R 6 B 6 R 7 B 7 R 5 B 8 R 9 B 9 R 8 B [出力例] 3 2 [入力例] 20 16 1 R 3 B 2 R 3 R 1 B 2 B 4 B 5 R 6 R 5 B 4 R 6 B 7 R 8 R 7 B 8 B 11 R 10 B 12 R 11 B 13 R 12 B 14 R 13 B 10 R 14 B 15 R 16 R 16 B 17 B 15 B 17 R [出力例] 5 4 |