C++の練習を兼ねて, AtCoder Beginner Contest 201 の 問題E (Xor Distances) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 実装に非常に苦労したものの, XOR計算, および, 幅優先探索 を 復習することが出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 201 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc201/editorial/1827 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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 = 1e9 + 7; struct edge{ int t; // 次の頂点. LL c; // コスト. }; vector<edge> G[202020]; LL d[202020]; LL xDist[66][2]; // kビット目が, 0, 1 である頂点の個数を保存. int memo[202020]; // 訪問済みフラグ. int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N - 1){ int u, v; LL w; scanf("%d %d %lld", &u, &v, &w); u--, v--; edge e; e.t = v; e.c = w; G[u].pb(e); e.t = u; e.c = w; G[v].pb(e); } // 2. 頂点 1 から 各頂点までの距離を計算. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](int s){ // 2-1. 空のキュー. queue<int> q; // 2-2. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 2-3. キューから取り出す. int u = q.front(); q.pop(); // 2-4. 取り出した要素を処理. for(auto &e : G[u]){ // 2-5. XORを計算. if(!memo[e.t] && e.t != s){ d[e.t] = d[u] ^ e.c; memo[e.t] = memo[u] + 1; q.push(e.t); } } } return; }; bfs(0); // 3. 2 の 冪乗 を 保存(通常版, MOD版). vl cPow2, mPow2; int count = 0; cPow2.pb(1); mPow2.pb(1); while(count < 61){ // 通常版. LL p = 2 * cPow2.back(); cPow2.pb(p); // MOD版. LL q = 2 * mPow2.back(); q %= MOD; mPow2.pb(q); // インクリメント. count++; } // 4. 各ビットに関して, 0, 1 となる頂点の個数を保存. rep(i, N){ rep(j, 61){ if(d[i] & cPow2[j]) xDist[j][1]++; else xDist[j][0]++; } } // 5. 集計. LL ans = 0; rep(i, 61){ ans += (xDist[i][0] * xDist[i][1]) % MOD * mPow2[i] % MOD; ans %= MOD; } // 6. 出力. 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 78 79 80 81 82 83 84 85 86 87 88 89 90 |
[入力例] 3 1 2 1 1 3 3 [出力例] 6 ※AtCoderテストケースより [入力例] 5 3 5 2 2 3 2 1 5 1 4 5 13 [出力例] 62 ※AtCoderテストケースより [入力例] 10 5 7 459221860242673109 6 8 248001948488076933 3 5 371922579800289138 2 5 773108338386747788 6 10 181747352791505823 1 3 803225386673329326 7 8 139939802736535485 9 10 657980865814127926 2 4 146378247587539124 [出力例] 241240228 ※AtCoderテストケースより [入力例] 15 1 2 66 1 3 56 1 14 116 2 13 38 2 7 35 3 8 62 3 4 119 3 5 100 8 11 61 8 12 24 12 15 98 5 6 51 6 10 17 6 9 33 [出力例] 6676 [入力例] 30 1 2 35602115828 1 3 22757985030 12 1 57881173395 3 23 31451467027 2 4 71178814495 2 5 70797358384 4 13 16378852590 4 14 11561949674 14 15 82226686406 15 24 18199117551 15 25 89529557518 15 26 40691756988 3 6 89216868118 3 7 35330113570 6 17 50417795719 6 16 41609715734 7 11 62551724670 7 8 12021988188 11 20 9352400257 11 21 26634079489 11 22 9183357474 8 9 48768608557 8 10 61676251453 10 18 96417487449 10 19 4131160740 18 29 90504109457 18 30 78998085309 19 27 82962407376 19 28 8006021346 [出力例] 134435348 |