C++の練習を兼ねて, AtCoder Beginner Contest 235 の 問題C (Counting 2) ～ 問題D (Neighbors) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞ることが出来たので, AC版に到達できたと思う.
2. UnionFind木 の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 231 解説 を ご覧下さい.
■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 |
// 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--) #define pb push_back #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); vi a(N); rep(i, N) scanf("%d", &a[i]); // 2. sort. sort(all(a)); // 3. クエリ回答. rep(i, Q){ int x; scanf("%d", &x); int ans = N - (lower_bound(all(a), x) - a.begin()); 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 |
[入力例] 3 1 100 160 130 120 [出力例] 2 ※AtCoderテストケースより [入力例] 5 5 1 2 3 4 5 6 5 4 3 2 [出力例] 0 1 2 3 4 ※AtCoderテストケースより [入力例] 5 5 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 [出力例] 5 3 5 5 5 ※AtCoderテストケースより [入力例] 10 5 112 20 72 91 60 54 58 5 66 39 97 20 113 80 3 [出力例] 1 9 0 2 10 |
■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 |
// 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 // 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. 人 A, B が 隣り合うように出来るか？ // -> 一列に並べる必要があることに注意. vvi G(N); UnionFind uf(N + 2); bool ok = true; rep(i, M){ int a, b; scanf("%d %d", &a, &b); a--; b--; G[a].pb(b); G[b].pb(a); // 次数チェック. if(G[a].size() > 2 || G[b].size() > 2) ok = false; // 閉路チェック. // -> 閉路があると, 横一列に並べることが出来なくなる. if(!uf.same(a, b)) uf.unite(a, b); else ok = false; } // 3. 出力. printf("%s\n", ok ? "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 |
[入力例] 4 2 1 3 2 3 [出力例] Yes ※AtCoderテストケースより [入力例] 4 3 1 4 2 4 3 4 [出力例] No ※AtCoderテストケースより [入力例] 10 5 6 7 1 2 1 10 2 6 3 5 [出力例] Yes [入力例] 10 7 5 8 4 5 1 4 1 7 7 9 1 6 2 3 [出力例] No [入力例] 10 10 1 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 [出力例] No |
■参照サイト
パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)
Union-Find木