C++の練習を兼ねて, AtCoder Beginner Contest 014 の 問題C (C – AtColor) ～ 問題D (D – 閉路) を解いてみた.
■感想.
1. C問題は, どこかでAtCoder上, 類題を解いたような記憶があるが, 思い出せなかった, 但し, 個人的には, 計算量を減らすためのテクニックが, 非常に面白く感じている.
2. D問題は, 時間かかってしまったが, 正答に辿り着けたので良かったと思う.
※但し, 以下の参照リンクにある Lowest Common Ancestor(LCA) のライブラリを使って対応している.
3. 新しい知識として, Lowest Common Ancestor(LCA) について, 確認出来たのが良かったと思う.
本家のサイトAtCoder Beginner Contest 014 解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; int enquete[1234321]; vector<int> dp(1234321); int main(){ // 1. 入力情報取得. int N; scanf("%d", &N); for(int i = 0; i < N; i++){ int a, b; scanf("%d %d", &a, &b); b++; enquete[a]++; enquete[b]--; } // for(int i = 0; i < 10; i++) printf("%d ", enquete[i]); // printf("\n"); // 2. アンケートの集計結果を移し替える. dp[0] = enquete[0]; for(int i = 1; i < 1234321; i++) dp[i] = dp[i - 1] + enquete[i]; // for(int i = 0; i < 10; i++) printf("%d ", dp[i]); // printf("\n"); // 3. 出力 ～ 後処理. printf("%d\n", *max_element(dp.begin(), dp.end())); 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 |
[入力例] 4 0 2 2 3 2 4 5 6 [出力例] 3 ※AtCoderテストケースより [入力例] 4 1000000 1000000 1000000 1000000 0 1000000 1 1000000 [出力例] 4 ※AtCoderテストケースより [入力例] 100 136503 224598 51762 227473 118706 691081 105346 164043 95202 286314 147233 1000000 61094 620146 71648 933208 23649 54046 86157 263199 85004 470255 60082 627227 68766 644867 24325 35614 55711 999999 711 796106 40687 999998 84349 387503 3580 317746 18768 767342 108388 373818 62692 568103 14337 588765 123410 536066 143583 985641 108777 533250 49973 314545 82427 279929 39612 999997 78370 543000 7161 927614 65274 65397 15537 634889 25676 531249 33818 255215 3237 453449 107745 107868 103907 810151 34446 837628 34974 489203 40306 62075 32991 735406 107029 891172 91407 640950 45380 608063 91619 999996 31057 336396 37763 633378 22130 999995 8508 785629 24537 761067 63997 64120 130679 424771 66233 783525 75690 985810 42724 151991 29494 994537 141443 999994 143276 642725 52379 696382 145141 196340 41983 638896 43539 974161 116923 117046 42087 137985 49647 328037 101449 396226 149746 477929 126780 999993 18620 802935 8983 594294 88445 502104 90562 90685 40269 573916 18692 841650 3219 893247 103796 999992 94320 216498 66610 815410 11425 791229 41143 79055 67395 460973 140620 140743 102016 730130 38544 250569 42694 918156 23922 999991 141635 676715 57294 514894 111019 825442 50344 596323 134441 581109 98751 98874 81459 696449 123639 694276 60057 515967 87253 437715 44599 292057 143235 896065 30291 193354 [出力例] 88 |
■C++版プログラム(問題D／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 |
// 以下のライブラリを使ってみる. // Another easy solution in <O(N logN, O(logN)> // https://www.topcoder.com/community/competitive-programming/tutorials/range-minimum-query-and-lowest-common-ancestor/#Lowest%20Common%20Ancestor%20(LCA) #include <bits/stdc++.h> using namespace std; const int MAXN = 100001; const int LOGMAXN = 17; // 2 の 17乗 … 131072 int L[MAXN], T[MAXN], P[MAXN][LOGMAXN]; // グラフの経路を探索する. // 深さ優先探索(depth-first search). // https://ja.wikipedia.org/wiki/深さ優先探索 // @param g: グラフ. // @param c: 探索地点となる頂点. // @param b: 探索地点から見て, 前回探索済の頂点. // @param d: 探索開始地点からの距離. // @return : 特に無し. void dfs(const vector<vector<int>> &g, int c, int b, int d){ L[c] = d, T[c] = b; for(auto &e : g[c]){ if(e == b) continue; dfs(g, e, c, d + 1); } } void prepare(int N){ // we initialize every element in P with -1. for(int i = 0; i < N; i++) for(int j = 0; 1 << j < N; j++) P[i][j] = -1; // the first ancestor of every node i is T[i]. for(int i = 0; i < N; i++) P[i][0] = T[i]; // bottom up dynamic programing. for(int j = 1; 1 << j < N; j++){ for(int i = 0; i < N; i++){ if(P[i][j - 1] != -1) P[i][j] = P[P[i][j - 1]][j - 1]; } } } int query(int N, int p, int q){ int log; // if p is situated on a higher level than q then we swap them. if(L[p] < L[q]) swap(p, q); // we compute the value of [log(L[p)]. for(log = 1; 1 << log <= L[p]; log++); log--; // we find the ancestor of node p situated on the same level with q using the values in P. for(int i = log; i >= 0; i--){ if(L[p] - (1 << i) >= L[q]) p = P[p][i]; if(p == q) return p; } // we compute LCA(p, q) using the values in P. for(int i = log; i >= 0; i--){ if(P[p][i] != -1 && P[p][i] != P[q][i]) p = P[p][i], q = P[q][i]; } return T[p]; } int main(){ // 1. 入力情報取得. int N; int x, y; scanf("%d", &N); vector<vector<int>> graph(N); for(int i = 0; i < N - 1; i++){ scanf("%d %d", &x, &y); x--, y--; graph[x].push_back(y); graph[y].push_back(x); } // for(auto &g : graph){ // for(int v : g) printf("%d ", v); // printf("\n"); // } // 2. 頂点 0 を 根 として, 各頂点までの距離を計算. dfs(graph, 0, -1, 0); // for(int i = 0; i < N; i++) printf("L[%d]=%d\n", i, L[i]); // for(int i = 0; i < N; i++) printf("T[%d]=%d\n", i, T[i]); // 3. 各クエリに対応する. prepare(N); int Q; int a, b; scanf("%d", &Q); while(Q--){ scanf("%d %d", &a, &b); a--, b--; int p = query(N, a, b); // printf("a=%d b=%d p=%d\n", a, b, p); int ans = (L[a] - L[p]) + (L[b] - L[p]) + 1; printf("%d\n", ans); } // 4. 後処理. 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 |
[入力例] 5 1 2 1 3 1 4 4 5 3 2 3 2 5 2 4 [出力例] 3 4 3 ※AtCoderテストケースより [入力例] 6 1 2 2 3 3 4 4 5 5 6 4 1 3 1 4 1 5 1 6 [出力例] 3 4 5 6 ※AtCoderテストケースより [入力例] 7 3 1 2 1 2 4 2 5 3 6 3 7 5 4 5 1 6 5 6 4 7 5 3 [出力例] 3 3 5 5 4 ※AtCoderテストケースより [入力例] 12 2 1 3 1 12 2 2 4 4 6 4 5 7 5 8 5 11 8 9 7 10 7 6 12 3 2 3 3 6 9 11 10 9 3 11 [出力例] 4 3 5 5 3 7 |
■参照サイト
AtCoder Beginner Contest 014
Lowest Common Ancestor(LCA)