C++の練習を兼ねて, AtCoder Beginner Contest 273 の 問題E (Notebook) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, 解説にあるように, 木 の 性質 を 利用したロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 273 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc273/editorial/5023 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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--) int o[505050]; // 各頂点に書き込まれた整数. int p[505050]; // 親頂点. int main(){ // 1. 入力情報. int Q; scanf("%d", &Q); // 2. クエリ回答. int cur = 0, v = 0; map<int, int> n; o[cur] = -1; rep(i, Q){ // クエリ入力情報. char c[11]; scanf("%s", c); string q(c); // ADD. if(q == "ADD"){ // 整数 x. int x; scanf("%d", &x); // 頂点を追加. ++v; // 頂点の親子関係を保存. p[v] = cur; o[v] = x; cur = v; } // DELETE. if(q == "DELETE"){ // 親頂点に移動. cur = p[cur]; } // SAVE. if(q == "SAVE"){ // 整数 y. int y; scanf("%d", &y); // 現在コマがある頂点を保存. n[y] = cur; } // LOAD. if(q == "LOAD"){ // 整数 z. int z; scanf("%d", &z); // ノート の z ページ目を参照し, 移動. cur = n[z]; } // 出力. printf("%d%s", o[cur], (i < Q - 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 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 205 206 207 208 209 210 211 212 213 214 215 216 217 218 |
[入力例] 11 ADD 3 SAVE 1 ADD 4 SAVE 2 LOAD 1 DELETE DELETE LOAD 2 SAVE 1 LOAD 3 LOAD 1 [出力例] 3 3 4 4 3 -1 -1 4 4 -1 4 ※AtCoderテストケースより [入力例] 21 ADD 4 ADD 3 DELETE ADD 10 LOAD 7 SAVE 5 SAVE 5 ADD 4 ADD 4 ADD 5 SAVE 5 ADD 2 DELETE ADD 1 SAVE 5 ADD 7 ADD 8 DELETE ADD 4 DELETE LOAD 5 [出力例] 4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1 ※AtCoderテストケースより [入力例] 5 ADD 2 SAVE 3 DELETE LOAD 3 ADD 3 [出力例] 2 2 -1 2 3 [入力例] 50 ADD 15 ADD 10 LOAD 15 ADD 19 LOAD 1 SAVE 5 DELETE ADD 20 LOAD 5 ADD 13 LOAD 19 SAVE 7 ADD 22 ADD 11 ADD 4 SAVE 18 ADD 6 SAVE 10 LOAD 16 LOAD 5 ADD 1 ADD 15 ADD 19 ADD 3 SAVE 12 ADD 7 DELETE LOAD 10 SAVE 10 ADD 7 DELETE ADD 18 SAVE 5 ADD 1 SAVE 5 LOAD 10 ADD 15 DELETE ADD 23 LOAD 5 DELETE SAVE 10 ADD 9 ADD 7 SAVE 15 ADD 25 LOAD 5 DELETE SAVE 14 ADD 7 [出力例] 15 10 -1 19 -1 -1 -1 20 -1 13 -1 -1 22 11 4 4 6 6 -1 -1 1 15 19 3 3 7 3 6 6 7 6 18 18 1 1 6 15 6 23 1 18 18 9 7 7 25 1 18 18 7 [入力例] 100 ADD 6 LOAD 9 SAVE 3 ADD 27 LOAD 3 DELETE ADD 7 ADD 7 DELETE SAVE 3 ADD 9 SAVE 28 LOAD 19 DELETE LOAD 16 ADD 24 SAVE 20 ADD 18 ADD 77 SAVE 10 LOAD 12 ADD 30 SAVE 15 ADD 16 SAVE 4 ADD 77 ADD 55 ADD 777 LOAD 8 ADD 10 LOAD 10 LOAD 25 ADD 88 DELETE ADD 77 DELETE ADD 77 SAVE 23 ADD 66 LOAD 25 ADD 27 ADD 111 LOAD 8 DELETE ADD 500 DELETE SAVE 18 SAVE 4 SAVE 3 SAVE 13 DELETE LOAD 28 SAVE 18 LOAD 2 LOAD 19 ADD 6 LOAD 27 ADD 3 DELETE ADD 123 ADD 3 SAVE 18 ADD 4 SAVE 25 DELETE ADD 8 ADD 17 SAVE 19 SAVE 25 DELETE SAVE 17 LOAD 25 LOAD 20 DELETE SAVE 8 ADD 27 LOAD 14 LOAD 11 ADD 8 ADD 111 SAVE 29 LOAD 1 LOAD 14 ADD 22 SAVE 26 SAVE 18 ADD 77 SAVE 8 LOAD 5 SAVE 20 ADD 20 SAVE 9 ADD 8 SAVE 23 LOAD 28 DELETE LOAD 18 ADD 11 SAVE 16 ADD 77 [出力例] 6 -1 -1 27 -1 -1 7 7 7 7 9 9 -1 -1 -1 24 24 18 77 77 -1 30 30 16 16 77 55 777 -1 10 77 -1 88 -1 77 -1 77 77 66 -1 27 111 -1 -1 500 -1 -1 -1 -1 -1 -1 9 9 -1 -1 6 -1 3 -1 123 3 3 4 4 3 8 17 17 17 8 8 17 24 -1 -1 27 -1 -1 8 111 111 -1 -1 22 22 22 77 77 -1 -1 20 20 8 8 9 7 22 11 11 77 |
■参照サイト
パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273）