C++の練習を兼ねて, AtCoder Beginner Contest 230 の 問題C (X drawing) ~ 問題D (Destroyer Takahashi) を解いてみた.
■感想.
1. 問題C, Dは, 方針を決めることができたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 230 解説 の 各リンク を ご覧下さい.
■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 42 43 44 45 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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 main(){ // 1. 入力情報. LL N, A, B, P, Q, R, S; scanf("%lld %lld %lld %lld %lld %lld %lld", &N, &A, &B, &P, &Q, &R, &S); // 2. 黒マス範囲. LL kMin1 = max(1 - A, 1 - B); LL kMax1 = min(N - A, N - B); LL kMin2 = max(1 - A, B - N); LL kMax2 = min(N - A, B - 1); // 3. 出力. LL a, b; rep(i, (int)(Q - P + 1)){ rep(j, (int)(S - R + 1)){ // 3-1. (A, B) からの移動距離. bool ok = false; a = (P + i) - A; b = (R + j) - B; // 3-2. 黒マスに該当するか? // パターン①. if(a == b && kMin1 <= a && a <= kMax1) ok = true; // パターン②. if(a + b == 0 && kMin2 <= a && a <= kMax2) ok = true; // 3-3. 出力. printf("%s", ok ? "#" : "."); } puts(""); } 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 |
[入力例] 5 3 2 1 5 1 5 [出力例] ...#. #.#.. .#... #.#.. ...#. ※AtCoderテストケースより [入力例] 5 3 3 4 5 2 5 [出力例] #.#. ...# ※AtCoderテストケースより [入力例] 1000000000000000000 999999999999999999 999999999999999999 999999999999999998 1000000000000000000 999999999999999998 1000000000000000000 [出力例] #.# .#. #.# ※AtCoderテストケースより [入力例] 11 6 6 1 11 1 11 [出力例] #.........# .#.......#. ..#.....#.. ...#...#... ....#.#.... .....#..... ....#.#.... ...#...#... ..#.....#.. .#.......#. #.........# [入力例] 12345 2020 2021 2017 2023 2018 2024 [出力例] #.....# .#...#. ..#.#.. ...#... ..#.#.. .#...#. #.....# |
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vp = vector<P>; #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 a first #define b second #define pb push_back #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N, D; scanf("%d %d", &N, &D); vp v; rep(i, N){ int l, r; scanf("%d %d", &l, &r); v.pb({r, l}); } // 2. sort. sort(all(v)); // 3. カウント. int ans = 0, minR = 1010101010; rep(i, N){ // [l, r] が 衝撃波 の 範囲 [minR, minR + D - 1] に 含まれるか? if(minR > v[i].a || minR + D - 1 < v[i].b){ minR = v[i].a; ans++; } } // 4. 出力. printf("%d\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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
[入力例] 3 3 1 2 4 7 5 9 [出力例] 2 ※AtCoderテストケースより [入力例] 3 3 1 2 4 7 4 9 [出力例] 1 ※AtCoderテストケースより [入力例] 5 2 1 100 1 1000000000 101 1000 9982 44353 1000000000 1000000000 [出力例] 3 ※AtCoderテストケースより [入力例] 20 5 12 17 77 84 40 51 119 125 73 85 113 119 70 79 10 13 70 82 27 31 20 27 116 119 2 4 72 79 17 28 7 17 109 113 86 88 108 109 39 43 [出力例] 8 [入力例] 50 10 1810 1903 936 945 12230 12323 4750 4752 8500 8529 3950 4032 10872 10884 3282 3353 6205 6215 116 196 2626 2703 10009 10011 10514 10549 7577 7593 9689 9761 8984 9096 1390 1466 7835 7852 4756 4761 7967 8045 3417 3525 4265 4352 1356 1476 8978 9080 4481 4542 8305 8424 2887 2949 2499 2620 7262 7380 5083 5172 793 884 1855 1902 7775 7864 248 345 7239 7268 815 863 1407 1412 10147 10260 4915 4996 11488 11510 2003 2014 2955 3020 5099 5109 5846 5939 6037 6154 1253 1266 8425 8465 5863 5918 9449 9505 9882 9957 [出力例] 37 |
■参照サイト
AtCoder Beginner Contest 230