C++の練習を兼ねて, 第八回 アルゴリズム実技検定 の 問題M (バランス) を解いてみた.
■感想.
1. 問題Mは, 方針が見えなかったので, 解説を参考に提出して, AC版に到達出来た.
2. 実装に苦労したものの, 個人的には, 各頂点に割り当て可能な, 0以上の整数が決まっていくロジックが面白いと感じた.
3. 幅優先探索の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト 第八回 アルゴリズム実技検定 の 各リンク を ご覧下さい.
■C++版プログラム(問題M/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 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 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 |
// 解き直し. // https://atcoder.jp/contests/past202109-open/editorial/2659 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using P = pair<int, 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 a first #define b second #define pb push_back set<P> C[101010]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vvi G(N); map<P, int> sum, use; rep(i, M){ int a, b, c; scanf("%d %d %d", &a, &b, &c); a--, b--; G[a].pb(b); G[b].pb(a); // 辺情報を保存. sum[{a, b}] = c; use[{a, b}] = 0; } // 2. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vvi &G, int s, int* memo){ // 空のキュー. queue<int> q; // 探索地点 s を 訪問. memo[s] = 1; C[s].insert({0, 1}); // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 取り出した要素を処理. for(auto &v : G[u]){ // 辺を設定. P eCur = {min(u, v), max(u, v)}; P cCur = *C[u].begin(); // 頂点が訪問済みで無い場合. if(!memo[v]){ // 訪問済みを設定. memo[v] = 1; q.push(v); use[eCur] = 1; // 隣接頂点の条件を設定. P cNex; cNex.a = sum[eCur] - cCur.a; // (p + x)型. if(cCur.b == 1) cNex.b = -1; // (q - x)型. if(cCur.b == -1) cNex.b = 1; // 保存. C[v].insert(cNex); // 次へ. continue; } // 頂点が訪問済みでも, 辺については, 未訪問の場合. if(!use[eCur]){ // 隣接頂点の条件を設定. P cNex; cNex.a = sum[eCur] - cCur.a; // (p + x)型. if(cCur.b == 1) cNex.b = -1; // (q - x)型. if(cCur.b == -1) cNex.b = 1; // 保存. C[v].insert(cNex); } } } return; }; // 3. 書き込む数に関する条件を抽出. int memo[N]; rep(i, N) memo[i] = 0; bfs(G, 0, memo); // 4. 区間をチェック. int cMin = -2020202020, cMax = 2020202020; set<int> st; bool ok = true; rep(i, N){ // (p + x)型, (q - x)型 を カウント. int pCount = 0, mCount = 0; for(auto &p : C[i]){ if(p.b == 1) pCount++; else mCount++; } // 両者のいずれかが, 二個以上ある. if(pCount > 1 || mCount > 1){ ok = false; break; } // (p + x)型, (q - x)型 が, 一個ずつある. if(pCount == 1 && mCount == 1){ int x = 0; for(auto &p : C[i]){ if(p.b == -1) x += p.a; else x -= p.a; } // 負数の場合. if(x < 0) ok = false; // 正数の場合. if(x >= 0){ // 偶数の場合. if(x % 2 == 0) st.insert(x / 2); // 奇数の場合. if(x % 2 != 0) ok = false; } // 次へ. continue; } // (p + x)型のみ. if(pCount == 1){ P p = *C[i].begin(); cMin = max(cMin, -p.a); } // (q - x)型のみ. if(mCount == 1){ P p = *C[i].begin(); cMax = min(cMax, p.a); } } // 5. 例外. // 5-1. 一意に定まる値が, 二通り以上存在する場合. if(st.size() > 1) ok = false; // 5-2. 大小逆転の場合. if(cMax < cMin) ok = false; // 5-3. 一意に定まる値が, 範囲外の場合. if(st.size() == 1){ int x = *st.begin(); if(x < cMin || x > cMax) ok = false; } // 5-4. 出力. if(!ok){ puts("-1"); return 0; } // 6. 上記以外. int x = cMin; if(st.size() == 1) x = *st.begin(); rep(i, N){ P p = *C[i].begin(); printf("%d\n", (p.b == 1) ? x + p.a : p.a - x); } 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 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 |
[入力例] 3 2 1 2 2 2 3 1 [出力例] 1 1 0 ※AtCoderテストケースより [入力例] 3 3 1 2 0 2 3 0 1 3 2 [出力例] -1 ※AtCoderテストケースより [入力例] 4 4 1 2 3 2 3 4 3 4 5 1 4 6 [出力例] -1 [入力例] 5 5 1 2 6 2 3 10 3 5 5 4 5 8 1 4 7 [出力例] 0 6 4 7 1 [入力例] 7 8 1 2 5 2 4 4 2 3 7 3 6 5 6 7 9 3 7 6 4 5 2 5 7 8 [出力例] -1 [入力例] 10 10 1 2 8 1 5 10 1 4 6 2 10 5 2 3 7 3 9 6 3 7 9 7 8 10 8 9 7 6 7 5 [出力例] 5 3 4 1 5 0 5 5 2 2 [入力例] 3 3 1 2 0 1 3 1 2 3 1 [出力例] 0 0 1 [入力例] 5 5 1 2 4 1 5 4 2 4 6 3 4 6 3 5 5 [出力例] -1 [入力例] 5 5 1 2 4 1 5 4 2 4 5 3 4 6 3 5 5 [出力例] 2 2 3 3 2 [入力例] 18 25 1 5 8 2 5 6 1 6 12 2 6 10 2 3 5 2 8 7 3 6 13 4 6 10 4 7 3 3 7 6 7 15 11 7 16 5 15 16 12 1 12 11 12 13 17 13 14 16 12 14 15 8 9 11 9 10 8 9 11 10 10 11 8 9 17 7 11 17 7 11 18 8 17 18 5 [出力例] 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 |
■参照サイト
第八回 アルゴリズム実技検定