C++の練習を兼ねて, AtCoder Beginner Contest 241 の 問題C (Construct Highway) ~ 問題D (Sequence Query) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題D は, 場合分けが多く, 実装に苦労したものの, std::multiset の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 241 解説 の 各リンク を ご覧下さい.
■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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vs = vector<string>; #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 int main(){ // 1. 入力情報. int N; scanf("%d", &N); vs v; rep(i, N){ char c[1010]; scanf("%s", c); string s(c); v.pb(s); } // 2. 黒マスが, 6つ以上連続するか?. bool ok = false; rep(i, N){ rep(j, N){ // 下. int c1 = 0; if(i < N - 5) rep(k, 6) if(v[i + k][j] == '#') ++c1; // 右. int c2 = 0; if(j < N - 5) rep(k, 6) if(v[i][j + k] == '#') ++c2; // 右下. int c3 = 0; if(i < N - 5 && j < N - 5) rep(k, 6) if(v[i + k][j + k] == '#') ++c3; // 左下. int c4 = 0; if(i < N - 5 && j >= 5) rep(k, 6) if(v[i + k][j - k] == '#') ++c4; // 判定. if(c1 >= 4) ok = true; if(c2 >= 4) ok = true; if(c3 >= 4) ok = true; if(c4 >= 4) ok = true; // 見つかった. if(ok) break; } // 見つかった. if(ok) break; } // 3. 出力. 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 |
[入力例] 8 ........ ........ .#.##.#. ........ ........ ........ ........ ........ [出力例] Yes ※AtCoderテストケースより [入力例] 6 ###### ###### ###### ###### ###### ###### [出力例] Yes ※AtCoderテストケースより [入力例] 10 .......... #..##..... .......... .......... ....#..... ....#..... .#...#..#. .......... .......... .......... [出力例] No ※AtCoderテストケースより [入力例] 6 ...... ....#. ...#.. ...... .#.... #..... [出力例] Yes [入力例] 6 ...... ...... ...... ...... ...... #...## [出力例] No [入力例] 13 ............. ............. ..#.#...#.#.. ............. ..#.#...#.#.. .....#.#..... ..#.#...#.#.. .....#.#..... ..#.#...#.#.. ............. ..#.#...#.#.. ............. ............. [出力例] 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 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// 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. 入力情報. int Q; scanf("%d", &Q); // 2. クエリ回答. multiset<LL> mst; rep(i, Q){ // 2-1. クエリ入力情報. int f; scanf("%d", &f); // 2-2. クエリ 1. if(f == 1){ LL x; scanf("%lld", &x); mst.insert(x); } // 2-3. クエリ 2. if(f == 2){ LL x, q = 0; int k; scanf("%lld %d", &x, &k); auto it = mst.upper_bound(x); // 空の場合. if(mst.empty()){ puts("-1"); continue; } // x が 小さい場合. if(x < *mst.begin()){ puts("-1"); continue; } // x が 大きい場合. if(x > *it){ --it; --k; q = *it; } // 繰り返し. while(k > 0){ if(it == mst.begin() || it == mst.end()) break; --it; --k; q = *it; } printf("%lld\n", (k == 0) ? q : -1); } // 2-4. クエリ 3. if(f == 3){ LL x, q = 0; int k; scanf("%lld %d", &x, &k); auto it = mst.lower_bound(x); // 空の場合. if(mst.empty()){ puts("-1"); continue; } // x が 大きい場合. if(x > *(--mst.end())){ puts("-1"); continue; } // 最終要素の次を指していた場合. if(it == mst.end()) --it; // 繰り返し. while(k > 0){ q = *it; ++it; --k; if(it == mst.end()) break; } printf("%lld\n", (k == 0) ? q : -1); } } 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 |
[入力例] 11 1 20 1 10 1 30 1 20 3 15 1 3 15 2 3 15 3 3 15 4 2 100 5 1 1 2 100 5 [出力例] 20 20 30 -1 -1 1 ※AtCoderテストケースより [入力例] 15 1 67 1 111 3 89 2 1 222 1 136 3 107 1 2 101 4 1 205 2 103 2 1 64 2 188 1 3 29 2 2 43 4 3 164 5 2 60 1 [出力例] -1 111 -1 -1 136 67 -1 -1 -1 [入力例] 50 1 200 1 199 1 100 3 89 2 1 234 3 107 2 2 101 1 2 103 2 1 136 1 64 2 188 1 3 29 2 2 12 4 3 164 3 1 205 2 60 1 1 118 3 151 4 2 74 5 1 7 3 92 5 2 182 5 3 247 1 3 30 4 1 208 2 125 4 3 172 4 2 151 5 1 88 1 77 2 35 2 1 98 3 146 2 1 178 2 95 2 2 158 5 1 167 1 250 2 89 1 2 57 4 1 145 2 94 2 1 101 2 152 4 1 101 2 88 4 1 97 3 80 5 3 195 4 2 38 3 [出力例] 199 200 100 -1 136 100 -1 234 -1 234 -1 200 7 -1 136 7 208 7 -1 200 77 88 88 -1 77 101 7 101 208 -1 |