C++の練習を兼ねて, AtCoder Beginner Contest 225 の 問題C (Calendar Validator) ～ 問題D (Play Train) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題D で, 標準ライブラリ std::deque を利用するロジックが, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 225 解説 の 各リンク を ご覧下さい.
■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 33 34 35 36 37 38 39 40 41 |
// 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 b[10101][7], m[7]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) rep(j, M) scanf("%d", &b[i][j]); // 2. 余り. // -> 006.txt などで, WA版となったので, ロジック修正. repx(i, 1, 8) m[i % 7] = i; // 3. 判定. // 3-1. 横方向. // -> 1ずつ増加しているか？ // 余りも考慮. bool ok = true; rep(i, N){ rep(j, M - 1){ if(b[i][j + 1] != b[i][j] + 1) ok = false; if(m[b[i][j + 1] % 7] < m[b[i][j] % 7]) ok = false; } } // 3-2. 縦方向. // -> 7ずつ増加しているか？ rep(j, M) rep(i, N - 1) if(b[i + 1][j] != b[i][j] + 7) ok = false; // 4. 出力. printf("%s\n", ok ? "Yes" : "No"); 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 |
[入力例] 2 3 1 2 3 8 9 10 [出力例] Yes ※AtCoderテストケースより [入力例] 2 1 1 2 [出力例] No ※AtCoderテストケースより [入力例] 10 4 1346 1347 1348 1349 1353 1354 1355 1356 1360 1361 1362 1363 1367 1368 1369 1370 1374 1375 1376 1377 1381 1382 1383 1384 1388 1389 1390 1391 1395 1396 1397 1398 1402 1403 1404 1405 1409 1410 1411 1412 [出力例] Yes ※AtCoderテストケースより [入力例] 7 5 990 991 992 993 994 997 998 999 1000 1001 1004 1005 1006 1007 1008 1011 1012 1013 1014 1015 1018 1019 1020 1021 1022 1025 1026 1027 1028 1029 1032 1033 1034 1035 1036 [出力例] Yes [入力例] 10 5 3296 3297 3298 3299 3300 3303 3304 3305 3306 3307 3310 3311 3312 3313 3314 3317 3318 3319 3320 3321 3324 3325 3326 3327 3328 3331 3332 3333 3334 3335 3338 3339 3340 3341 3342 3345 3346 3347 3348 3349 3352 3353 3354 3355 3356 3359 3360 3361 3362 3363 [出力例] No [入力例] 20 3 5168 5169 5170 5175 5176 5177 5182 5183 5184 5189 5190 5191 5196 5197 5198 5203 5204 5205 5210 5211 5212 5217 5218 5219 5224 5225 5226 5231 5232 5233 5238 5239 5240 5245 5246 5247 5252 5253 5254 5259 5260 5261 5266 5267 5268 5273 5274 5275 5280 5281 5282 5287 5288 5289 5294 5295 5296 5301 5302 5303 [出力例] Yes |
■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 |
// 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--) #define pof pop_front #define pob pop_back #define puf push_front #define pub push_back int p[101010], q[101010]; int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); // 2. 初期化. rep(i, N) p[i] = q[i] = -1; // 3. クエリ回答. rep(i, Q){ // 3-1. クエリ入力情報. int c; scanf("%d ", &c); // 3-2. クエリ 1. if(c == 1){ int x, y; scanf("%d %d", &x, &y); --x; --y; // 電車 y の 親 を 電車 x と 設定. p[y] = x; q[x] = y; } // 3-3. クエリ 2. if(c == 2){ int x, y; scanf("%d %d", &x, &y); --x; --y; // 電車 x, y の 親子関係 を 廃止. p[y] = -1; q[x] = -1; } // 3-4. クエリ 3. if(c == 3){ int x; scanf("%d", &x); --x; // 電車 x の 親. int cur = x; deque<int> dq; while(cur != -1){ dq.puf(cur); cur = p[cur]; } // 電車 x の 子. cur = x; dq.pob(); while(cur != -1){ dq.pub(cur); cur = q[cur]; } // 出力. int M = dq.size(); printf("%d ", M); rep(i, M) printf("%d%s", dq[i] + 1, (i < M - 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 |
[入力例] 7 14 1 6 3 1 4 1 1 5 2 1 2 7 1 3 5 3 2 3 4 3 6 2 3 5 2 4 1 1 1 5 3 2 3 4 3 6 [出力例] 5 6 3 5 2 7 2 4 1 5 6 3 5 2 7 4 1 5 2 7 1 4 2 6 3 ※AtCoderテストケースより [入力例] 12 25 1 1 2 3 1 1 2 3 1 5 7 1 8 9 1 11 12 2 8 9 1 10 8 1 3 10 3 3 1 6 4 2 2 3 1 2 6 1 4 5 3 5 1 7 3 3 10 2 4 5 3 7 1 12 5 2 3 10 3 5 1 4 9 1 9 11 3 12 [出力例] 2 1 2 5 1 2 3 10 8 6 1 2 6 4 5 7 9 1 2 6 4 5 7 3 10 8 5 5 7 3 10 8 5 11 12 5 7 3 10 1 2 6 4 9 11 12 5 7 3 |
■参照サイト
UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225)