C++の練習を兼ねて, AtCoder Regular Contest 063 の 問題E (木と整数) を解いてみた.
■感想.
1. 問題E は, 解答方針が, 全く見えなかったので, 解答を参照して, 実装して何とかAC版となった.
2. 最初, テストケース(random2_05.txt, random2_06.txt)で, WA版となったが, 根だけでなく, 各頂点についても, 区間 が 正しく設定されているか確認する処理を追加したところ, エラーを解消できた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 063 解説をご覧下さい.
■C++版プログラム(問題E／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 193 194 195 196 197 198 199 200 201 202 203 204 |
// 解き直し. // https://img.atcoder.jp/data/arc/063/editorial.pdf #include <bits/stdc++.h> using namespace std; using vvi = vector<vector<int>>; 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 pb push_back #define a first #define b second const int LIMIT = 101010; int d[LIMIT]; // 根 からの 距離 を 保存. int p[LIMIT]; // 頂点に書き込んだ整数(0以上). int l[LIMIT]; // 頂点に書き込める最小値. int r[LIMIT]; // 頂点に書き込める最大値. int ans[LIMIT]; // 頂点に書き込み整数. // グラフを幅優先探索する. // https://ja.wikipedia.org/wiki/幅優先探索 // ※bfsの動作確認用. // @param G: グラフ. // @param s: グラフの探索開始頂点. // @param d: 探索開始地点からの距離. // @return: 特に無し. void bfs(vvi &G, int s, int* d){ // 1. 空のキュー. queue<int> q; // 2. 訪問済みフラグ設定. // ※スタート地点は, 距離ゼロを指定. d[s] = 0; // 3. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 4. キューから取り出す. int u = q.front(); q.pop(); // 5. 取り出した要素を処理. for(auto &e : G[u]){ // 6. 訪問済であれば, 処理をスキップ. if(d[e]) continue; if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e); } } return; } int main(){ // 1. 入力情報. int N; scanf("%d", &N); vvi G(N); rep(i, N - 1){ int a, b; scanf("%d %d", &a, &b); a--, b--; G[a].pb(b); G[b].pb(a); } int K, root = -1; scanf("%d", &K); rep(i, LIMIT) p[i] = -1; rep(i, K){ int a, b; scanf("%d %d", &a, &b); a--; p[a] = b; if(root == -1) root = a; // 根を取得. } assert(root != -1); // 2. 区間初期化. rep(i, N) l[i] = -1010101010, r[i] = 1010101010; rep(i, N) if(p[i] != -1) l[i] = p[i], r[i] = p[i]; // 3. 根 から 各頂点までの距離を計算. bfs(G, root, d); // rep(i, N) printf("%d ", d[i]); // puts(""); // 4. 偶奇の制約を満たすか確認. int sign = p[root] & 1; bool f = true; rep(i, N){ // すでに書き込みある頂点で確認. if(p[i] != -1){ // 根 からの 距離の偶奇で分岐. if(d[i] & 1){ // 根からの距離が, 奇数の場合に, 根に書かれた整数の偶奇と同じ場合. if((p[i] & 1) == sign){ f = false; break; } }else{ // 根からの距離が, 偶数の場合に, 根に書かれた整数の偶奇と異なる場合. if((p[i] & 1) != sign){ f = false; break; } } } } if(!f){ puts("No"); return 0; } // 5. 根 から 遠い順, 近い順 に並び替え. // {距離, 頂点番号} priority_queue<P> fPq; priority_queue<P, vector<P>, greater<P>> nPq; rep(i, N){ // {距離, 頂点番号} fPq.push({d[i], i}); nPq.push({d[i], i}); } // 6. 区間更新. while(!fPq.empty()){ // 6-1. 頂点 v を一つ取り出す. P x = fPq.top(); fPq.pop(); // 6-2. 頂点 v の 頂点番号は？ int v = x.b; // 6-4. 頂点 v の 親頂点 の 区間 を 更新. for(auto &u : G[v]){ // 頂点 v の 親頂点 u を 選択. if(d[u] < d[v]){ // 区間を更新. l[u] = max(l[u], l[v] - 1); r[u] = min(r[u], r[v] + 1); } } } // rep(i, N) printf("%d %d %d\n", i, l[i], r[i]); // 7. 根の区間を確認. if(l[root] > r[root]){ puts("No"); return 0; } // 8. 各頂点に書き出す整数を保存. while(!nPq.empty() && f){ // 8-1. 頂点 v を一つ取り出す. P x = nPq.top(); nPq.pop(); // 8-2. 頂点 v の 頂点番号は？ int v = x.b; // random2_05.txt, random2_06.txt で WA版だったため, ロジック追加. // 8-3. 頂点 v の 区間 を確認. if(l[v] > r[v]){ // random2_05.txt の 場合は, 以下のケースで, 成立しない区間 を 確認できた. // l[58966]=499995 r[58966]=499993 // printf("l[%d]=%d r[%d]=%d\n", v, l[v], v, r[v]); f = false; break; } // 8-4. 頂点 v の 値 を 設定. if(p[v] != -1) ans[v] = p[v]; // 8-5. 頂点 v の 親頂点 の 区間 から, 子頂点 に 書き込む値を絞り込む. if(p[v] == -1){ int pVal = 1010101010; for(auto &u : G[v]){ // 頂点 v の 親頂点 u の 整数 を 保存(※親頂点は, 一つの筈). if(d[u] < d[v]){ pVal = ans[u]; break; } } assert(pVal != 1010101010); // 区間と照合して, 条件に合うものを設定. // なければ, false. int pLVal = pVal - 1; int pRVal = pVal + 1; if(pLVal >= l[v] && pLVal <= r[v]) ans[v] = pLVal; else if(pRVal >= l[v] && pRVal <= r[v]) ans[v] = pRVal; else f = false; } } // 9. 出力. if(f){ puts("Yes"); rep(i, N) printf("%d\n", ans[i]); }else{ puts("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 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 |
[入力例] 5 1 2 3 1 4 3 3 5 2 2 6 5 7 [出力例] Yes 5 6 6 5 7 ※AtCoderのテストケースより [入力例] 5 1 2 3 1 4 3 3 5 3 2 6 4 3 5 7 [出力例] No ※AtCoderのテストケースより [入力例] 4 1 2 2 3 3 4 1 1 0 [出力例] Yes 0 -1 -2 -3 ※AtCoderのテストケースより [入力例] 6 1 3 3 2 3 4 3 5 2 6 2 3 5 6 7 [出力例] Yes 4 6 5 4 4 7 [入力例] 15 1 2 3 2 3 4 3 5 1 6 1 7 1 8 7 11 7 12 7 13 5 9 5 10 10 14 10 15 5 2 5 5 3 8 7 12 6 14 1 [出力例] Yes 6 5 4 3 3 5 5 7 2 2 4 6 4 1 1 [入力例] 5 2 3 3 1 1 4 4 5 2 2 5 4 8 [出力例] Yes 7 5 6 8 7 |
■参照サイト
AtCoder Regular Contest 063