C++の練習を兼ねて, AtCoder Beginner Contest 247 の 問題F (Cards) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 247 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F/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 89 90 |
// 解き直し. // https://atcoder.jp/contests/abc247/editorial/3719 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using LL = long long; #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 LL MOD = 998244353; LL f[202020], g[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vi p(N), q(N); rep(i, N) scanf("%d", &p[i]); rep(i, N) scanf("%d", &q[i]); // 2. 関数 f. f[1] = 2; f[2] = 3; repx(i, 3, 202020){ f[i] = f[i - 1] + f[i - 2]; f[i] %= MOD; } // 3. 関数 g. g[1] = 1; g[2] = 3; g[3] = 4; repx(i, 4, 202020){ g[i] = f[i - 1] + f[i - 3]; g[i] %= MOD; } // 4. グラフ作成. vvi G(N); rep(i, N){ G[p[i] - 1].pb(q[i] - 1); G[q[i] - 1].pb(p[i] - 1); } // 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[N], idx = 0; rep(i, N) c[i] = 0; rep(i, N) if(!c[i]) bfs(G, i, c, ++idx); // 6. 各連結成分のサイズ. int cs[idx + 1]; rep(i, idx + 1) cs[i] = 0; rep(i, N) cs[c[i]]++; // 7. 集計. LL ans = 1; repx(i, 1, idx + 1){ ans *= g[cs[i]]; ans %= MOD; } // 8. 出力. 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 |
[入力例] 3 1 2 3 2 1 3 [出力例] 3 ※AtCoderテストケースより [入力例] 5 2 3 5 4 1 4 2 1 3 5 [出力例] 12 ※AtCoderテストケースより [入力例] 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 [出力例] 1 ※AtCoderテストケースより [入力例] 4 1 2 3 4 4 3 2 1 [出力例] 9 [入力例] 7 3 1 4 7 5 2 6 2 6 3 4 5 1 7 [出力例] 18 [入力例] 20 1 4 15 6 18 13 8 2 14 12 10 19 11 17 3 20 16 7 5 9 9 17 1 7 11 12 20 15 14 4 6 2 13 16 3 10 18 5 8 19 [出力例] 5742 [入力例] 50 8 15 30 37 2 20 26 36 12 18 19 43 22 39 41 7 27 33 35 14 5 10 11 49 47 32 6 25 17 38 4 23 13 34 46 29 1 44 45 24 28 21 40 16 48 3 42 9 50 31 32 10 7 22 17 12 50 11 39 16 15 9 4 37 38 27 41 26 35 5 45 23 29 44 6 49 36 8 40 18 24 43 1 20 33 3 14 28 19 34 42 21 47 31 25 30 2 13 46 48 [出力例] 2792548 [入力例] 100 12 17 75 1 46 13 68 29 62 51 90 16 14 73 71 79 22 70 72 27 64 42 4 30 88 85 93 18 19 99 48 91 24 60 9 44 100 47 43 15 37 82 25 67 76 69 81 50 32 20 26 58 49 77 7 45 78 84 94 98 2 33 87 80 56 5 96 11 65 59 36 92 54 21 8 89 35 66 83 86 39 3 74 10 97 31 53 52 34 6 40 57 61 23 95 63 41 55 38 28 59 91 23 2 44 84 78 24 54 74 97 45 8 61 63 68 57 64 87 62 47 66 98 11 12 1 52 10 22 81 50 77 42 17 7 46 76 73 43 86 6 82 85 27 40 48 94 60 15 72 80 19 55 34 14 99 28 35 25 65 89 88 92 70 37 31 38 5 53 93 41 75 9 29 21 13 67 58 16 96 90 71 69 79 32 49 33 39 3 56 4 100 95 36 83 30 51 26 20 18 [出力例] 695670925 |
■参照サイト
AtCoder Beginner Contest 247