C++の練習を兼ねて, AtCoder Regular Contest 102 の 問題D (D – All Your Paths are Different Lengths) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を参照して, 実装した.
2. ほぼ, 解説通りに実装できたと思う.
3. 1年以上前に, AtCoder Beginner Contest 108 の 問題D（All Your Paths are Different Lengths）として, 復習していたが, 記憶から, ほとんど消えていたようである.
今回, 改めて復習して良かったと思う.
本家のサイトARC 102解説をご覧下さい.
■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 |
// 解き直し. // ARC 102解説. // https://img.atcoder.jp/arc102/editorial.pdf #include <bits/stdc++.h> using namespace std; #define pb push_back #define p1 first #define p2 second const int MAX_N = 21; typedef pair<int, int> pii; vector<vector<pii>> graph(MAX_N); int pow2[MAX_N]; int main(){ // 1. 入力情報取得. int L; scanf("%d", &L); // 2. 解説通り. // 2-1. 頂点 i から 頂点 i + 1 へ, 長さ 0, pow2[i - 1] の 辺を, 1本ずつ張る. int r = 0, M = 0; pow2[0] = 1; for(int i = 1; i < MAX_N; i++){ pow2[i] = pow2[i - 1] * 2; if(pow2[i] <= L) r++; } int N = r + 1; for(int i = 1; i < N; i++){ graph[i].pb({i + 1, 0}); graph[i].pb({i + 1, pow2[i - 1]}); M += 2; } // 2-2. 条件を確認しながら, 頂点 t から 頂点 N に, 長さ L - pow2[t - 1] の 辺を, 1本ずつ張る. for(int t = N - 1; t >= 1; t--){ if(L - pow2[t - 1] >= pow2[r]){ graph[t].pb({N, L - pow2[t - 1]}); L -= pow2[t - 1]; M++; } } // 3. 出力. printf("%d %d\n", N, M); for(int i = 1; i <= N; i++){ for(auto &o : graph[i]) printf("%d %d %d\n", i, o.p1, o.p2); } 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 |
[入力例] 2 [出力例] 2 2 1 2 0 1 2 1 [入力例] 3 [出力例] 2 3 1 2 0 1 2 1 1 2 2 [入力例] 4 [出力例] 3 4 1 2 0 1 2 1 2 3 0 2 3 2 ※AtCoderテストケースより [入力例] 5 [出力例] 3 5 1 2 0 1 2 1 1 3 4 2 3 0 2 3 2 ※AtCoderテストケースより [入力例] 6 [出力例] 3 5 1 2 0 1 2 1 2 3 0 2 3 2 2 3 4 [入力例] 123456 [出力例] 17 37 1 2 0 1 2 1 2 3 0 2 3 2 3 4 0 3 4 4 4 5 0 4 5 8 5 6 0 5 6 16 6 7 0 6 7 32 7 8 0 7 8 64 7 17 65536 8 9 0 8 9 128 9 10 0 9 10 256 10 11 0 10 11 512 10 17 65600 11 12 0 11 12 1024 12 13 0 12 13 2048 13 14 0 13 14 4096 14 15 0 14 15 8192 14 17 66112 15 16 0 15 16 16384 15 17 74304 16 17 0 16 17 32768 16 17 90688 [入力例] 654321 [出力例] 20 51 1 2 0 1 2 1 1 20 524288 2 3 0 2 3 2 3 4 0 3 4 4 4 5 0 4 5 8 5 6 0 5 6 16 5 20 524289 6 7 0 6 7 32 6 20 524305 7 8 0 7 8 64 7 20 524337 8 9 0 8 9 128 8 20 524401 9 10 0 9 10 256 9 20 524529 10 11 0 10 11 512 10 20 524785 11 12 0 11 12 1024 12 13 0 12 13 2048 12 20 525297 13 14 0 13 14 4096 13 20 527345 14 15 0 14 15 8192 14 20 531441 15 16 0 15 16 16384 15 20 539633 16 17 0 16 17 32768 16 20 556017 17 18 0 17 18 65536 17 20 588785 18 19 0 18 19 131072 19 20 0 19 20 262144 |
■参照サイト
AtCoder Regular Contest 102