C++の練習を兼ねて, AtCoder Beginner Contest 219 の 問題G (Propagation) を解いてみた.
■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. (競プロ典型 90 問 の 問題083 (Colorful Graph))に, 類似している印象を受けたものの, AC版となるための実装までに, 苦労したように思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 219 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題G／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 |
// 解き直し. // https://atcoder.jp/contests/abc219/editorial/2653 // https://atcoder.jp/contests/typical90/tasks/typical90_ce // -> 003.txt などのテストケースで, WA版となったため, ロジック修正. // 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 pb push_back #define a first #define b second P n[202020]; // {頂点番号, {クエリ番号, 整数}}. P q[202020]; // {頂点番号, {クエリ番号, 整数}}(※看板). int main(){ // 1. 入力情報. int N, M, Q; scanf("%d %d %d", &N, &M, &Q); vvi G(N), F(N); rep(i, M){ int a, b; scanf("%d %d", &a, &b); a--, b--; G[a].pb(b); G[b].pb(a); } // 2. 部分グラフ作成(次数が大きい頂点に向かう頂点のみ辺を追加). int B = (int)sqrt(M); rep(i, N) if(G[i].size() >= B) for(auto &p : G[i]) F[p].pb(i); // 3. クエリ実行. rep(i, N) n[i].a = -1, n[i].b = i + 1; rep(i, N) q[i].a = -1, q[i].b = 0; rep(i, Q){ // 3-1. クエリ入力情報. int x; scanf("%d", &x); x--; // 3-2. (手順 1) 頂点 x の整数を正しい値に書き換え. // -> 一番直近のクエリ番号(値が最も大きいもの)で更新された内容を反映. for(auto &u : F[x]){ if(q[u].a > n[x].a){ n[x].a = q[u].a; n[x].b = q[u].b; } } // 3-3. (手順 2) 頂点 xの正しい整数を X とおく. int X = n[x].b; // 3-4. (手順 3) 頂点 xの次数が B 以上か否か応じて, 処理を分岐. int gSize = G[x].size(); // (a) 隣接する頂点数が小さい場合. if(gSize < B){ for(auto &u : G[x]){ n[u].a = i; n[u].b = X; } } // (b) 隣接する頂点数が大きい場合. if(gSize >= B){ q[x].a = i; q[x].b = X; } } // 4. 復元. rep(i, N){ // 隣接する頂点数が大きい頂点を基準に, 各頂点 の 整数を正しい値に書き換え. // -> グラフ F は, 構成上, 利用できないことに注意. int gSize = G[i].size(); if(gSize >= B){ for(auto &u : G[i]){ if(q[i].a > n[u].a){ n[u].a = q[i].a; n[u].b = q[i].b; } } } } // 5. 出力. rep(i, N){ printf("%d", n[i].b); printf("%s", (i < N - 1) ? " " :"\n"); } 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 |
[入力例] 5 6 3 4 2 4 3 1 2 2 3 4 5 1 5 1 3 4 [出力例] 1 3 3 3 3 ※AtCoderテストケースより [入力例] 14 14 8 7 4 13 9 9 8 4 3 7 2 13 8 12 8 11 3 6 3 7 14 6 5 1 4 10 13 5 2 2 6 12 9 1 10 5 4 [出力例] 1 6 1 1 6 6 1 9 9 10 11 12 10 14 ※AtCoderテストケースより [入力例] 1 0 1 1 [出力例] 1 [入力例] 3 2 3 2 1 3 2 3 1 2 [出力例] 1 1 1 [入力例] 11 13 5 2 1 2 10 2 9 10 9 2 4 4 5 4 3 3 5 3 7 3 6 7 8 8 7 8 11 7 3 1 2 11 [出力例] 1 1 7 1 7 7 7 11 1 1 11 [入力例] 22 27 8 1 17 1 5 1 6 6 5 17 18 18 19 19 17 12 1 12 13 13 14 14 12 15 13 15 14 15 16 16 13 2 3 3 4 4 2 4 20 21 20 20 22 21 22 7 8 9 8 10 9 10 11 11 7 5 18 17 12 15 3 4 7 [出力例] 12 3 3 3 5 5 7 7 9 10 7 12 15 15 15 15 18 18 18 3 21 22 [入力例] 13 12 5 1 2 1 3 1 4 1 5 1 6 1 7 8 7 8 9 8 10 8 11 8 12 8 13 1 8 1 8 1 [出力例] 1 1 1 1 1 1 1 8 8 8 8 8 8 [入力例] 15 14 10 1 10 1 3 1 6 1 14 14 15 10 11 10 12 10 13 3 2 3 4 3 5 6 7 6 8 6 9 1 14 15 7 6 5 3 11 10 14 [出力例] 1 5 5 5 5 7 7 7 7 11 11 11 11 1 1 |
■参照サイト
サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）
083 – Colorful Graph