C++の練習を兼ねて, AtCoder Regular Contest 107 の 問題C (Shuffle Permutation) を解いてみた.
■感想.
1. C問題は, 方針が見えなかったので, 解説を参照して実装して, ようやく, AC版となった.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 107 解説 の 各リンク を ご覧下さい.
■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 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 |
// 解き直し. // https://atcoder.jp/contests/arc107/editorial/266 // C++(GCC 9.2.1) #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 LL MOD = 998244353; int a[55][55]; LL FAC[55]; int rConnection[55], cConnection[55]; // 連結成分番号を保存. LL rAppearance[55], cAppearance[55]; // 連結成分番号の出現回数. // https://ja.wikipedia.org/wiki/幅優先探索 // ※bfsの動作確認用. // @param G: グラフ. // @param s: グラフの探索開始頂点. // @param c: 連結成分番号の保存領域. // @param l: 連結成分番号(※1以上). // @return: 特に無し. void bfs(vvi &G, int s, int* c, int l){ // 1. 空のキュー. queue<int> q; // 2. 連結成分番号を設定. c[s] = l; // 3. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 4. キューから取り出す. int u = q.front(); q.pop(); // 5. 取り出した要素を処理. for(auto &e : G[u]){ // 6. 訪問済であれば, 処理をスキップ. if(c[e]) continue; if(!c[e] && e != s) c[e] = l, q.push(e); } } return; } int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); rep(i, N) rep(j, N) scanf("%d", &a[i][j]); // 2. 階乗計算. FAC[0] = 1; repx(i, 1, 55) FAC[i] = FAC[i - 1] * (LL)i, FAC[i] %= MOD; // 3. グラフ作成. vvi rG(N), cG(N); rep(i, N){ repx(j, i + 1, N){ // 行方向. bool rOk = true; rep(k, N) if(a[i][k] + a[j][k] > K) rOk = false; if(rOk) rG[i].pb(j), rG[j].pb(i); // 列方向. bool cOk = true; rep(k, N) if(a[k][i] + a[k][j] > K) cOk = false; if(cOk) cG[i].pb(j), cG[j].pb(i); } } // 4. 探索を行い, 連結成分に分割. int rIdx = 0, cIdx = 0; rep(i, N){ if(!rConnection[i]) bfs(rG, i, rConnection, ++rIdx); if(!cConnection[i]) bfs(cG, i, cConnection, ++cIdx); } // 5. 各連結成分番号の出現回数を計算. rep(i, N) rAppearance[rConnection[i]]++, cAppearance[cConnection[i]]++; // 6. 集計. LL ans = 1; repx(i, 1, rIdx + 1) ans *= FAC[rAppearance[i]], ans %= MOD; repx(i, 1, cIdx + 1) ans *= FAC[cAppearance[i]], ans %= MOD; // 7. 出力. 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 |
[入力例] 3 13 3 2 7 4 8 9 1 6 5 [出力例] 12 ※AtCoderのテストケースより [入力例] 10 165 82 94 21 65 28 22 61 80 81 79 93 35 59 85 96 1 78 72 43 5 12 15 97 49 69 53 18 73 6 58 60 14 23 19 44 99 64 17 29 67 24 39 56 92 88 7 48 75 36 91 74 16 26 10 40 63 45 76 86 3 9 66 42 84 38 51 25 2 33 41 87 54 57 62 47 31 68 11 83 8 46 27 55 70 52 98 20 77 89 34 32 71 30 50 90 4 37 95 13 100 [出力例] 348179577 ※AtCoderのテストケースより [入力例] 3 3 1 5 6 2 3 7 4 9 8 [出力例] 1 [入力例] 5 35 22 21 8 16 23 9 3 13 2 24 4 11 5 20 10 25 14 6 12 18 7 15 17 19 1 [出力例] 144 [入力例] 7 88 35 15 21 49 23 7 37 36 3 5 47 8 12 42 18 4 14 22 28 30 16 26 29 20 31 10 17 48 45 38 27 43 24 19 6 13 2 40 11 1 46 33 44 25 32 41 34 9 39 [出力例] 25401600 [入力例] 12 256 100 91 25 129 49 61 73 85 97 109 121 8 115 14 103 38 18 62 74 32 98 110 22 134 139 118 27 39 51 63 11 87 99 44 123 135 89 16 114 40 112 64 76 88 1 52 124 136 82 17 29 144 53 92 77 4 101 113 48 137 119 50 90 127 54 66 69 30 71 28 126 138 7 19 31 43 105 67 24 13 26 2 42 3 133 107 86 111 56 59 80 65 104 116 128 140 9 21 33 45 57 78 81 93 55 117 37 46 132 122 34 141 58 70 5 94 106 15 130 142 75 23 35 47 68 102 83 95 20 6 131 36 12 79 143 125 60 72 84 96 108 120 10 41 [出力例] 350016467 |
■参照サイト
AtCoder Regular Contest 107