C++の練習を兼ねて, AtCoder Regular Contest 155 の 問題A (ST and TS Palindrome) ~ 問題B (Abs Abs Function) を解いてみた.
■感想.
1. 問題A, B は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 155 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A/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 |
// 解き直し. // https://atcoder.jp/contests/arc155/editorial/5620 // 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--) #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. 回文判定. auto isPalindrome = [&](string s) -> bool { string r = s; reverse(all(r)); return (s == r); }; // 3. テストケース. rep(i, T){ // 3-1. 各テストケース. int N; LL k; scanf("%d %lld", &N, &k); char c[N + 1]; scanf("%s", c); string S(c); // 3-2. K の 置き換え. int K = (int)(k % (N * 2)); // 3-3. S' の 候補. // ex. // S = abracadabra, K = 15 のとき. // 左: arbadacarba.... // 右: ....arbadacarba // -> 区間[4, 10] を 比較して, 一致しないので, S' の候補は, 存在しない. // // S = opqrsopqrs, K = 15 の とき. // 左: srqposrqpo..... // 右: .....srqposrqpo // -> 区間[5, 9] を 比較して, 一致するので, S' の候補(srqposrqposrqpo)は, 存在する. // 但し, S + S', S' + S は 回文ではない. bool ok = true; string T(K, '.'); rep(j, min(N, K)) T[j] = S[N - 1 - j]; rep(j, min(N, K)){ if(T[K - 1 - j] == '.'){ T[K - 1 - j] = S[j]; continue; } if(T[K - 1 - j] != S[j]){ ok = false; break; } } // 3-4. S' の 候補なし. if(!ok){ puts("No"); continue; } // printf("T=%s\n", T.c_str()); // 3-5. 出力. printf("%s\n", (isPalindrome(S + T) && isPalindrome(T + S)) ? "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 |
[入力例] 2 6 2 abbaab 5 3 abcbb [出力例] Yes No ※AtCoderのテストケースより [入力例] 3 12 400378271514996652 njvhhvjnnjvh 10 884633988115575508 rrhiyvrrur 36 71630165869626180 vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh [出力例] Yes No Yes ※AtCoderのテストケースより [入力例] 10 1 1 a 3 3 abc 2 1 ab 3 5 cbaabccba 11 5 abracadabra 30 10 yyegvzokgmmgkozvgeyyyyegvzokgm 30 12 thluflfzefbdyexthluflfzefbdyex 18 6 pqrrqppqrrqppqrrqp 75 15 lksipgkfbetioayyaoitebfkgpiskllksipgkfbetioayyaoitebfkgpiskllksipgkfbetioay 210 30 xpzlrgriptctroyeiofevnizfqecskksceqfzinvefoieyortctpirgrlzpxxpzlrgriptctroyeiofevnizfqecskksceqfzinvefoieyortctpirgrlzpxxpzlrgriptctroyeiofevnizfqecskksceqfzinvefoieyortctpirgrlzpxxpzlrgriptctroyeiofevnizfqecsk [出力例] Yes Yes No No No Yes No Yes Yes Yes |
■C++版プログラム(問題B/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 |
// 解き直し. // https://atcoder.jp/contests/arc155/editorial/5594 // 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; LL A, B; scanf("%d %lld %lld", &Q, &A, &B); // 2. 初期化. set<LL> st; st.insert(-2020202020); st.insert(+2020202020); st.insert(A - B); st.insert(A + B); // 3. クエリ回答. rep(i, Q){ // 3-1. クエリ入力情報. int t; LL a, b; scanf("%d %lld %lld", &t, &a, &b); // 3-2. クエリ 1. if(t == 1){ st.insert(a - b); st.insert(a + b); } // 3-3. クエリ 2. if(t == 2){ // [a, b] に, 要素がある. auto ia = st.lower_bound(a); if(*ia <= b){ puts("0"); continue; } // [a, b] に, 要素がない. if(*ia >= a) --ia; LL L = *ia; LL R = *st.upper_bound(b); // 出力. printf("%lld\n", min(a - L, R - b)); } } 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 |
[入力例] 4 0 5 1 3 11 2 7 8 1 8 2 2 8 9 [出力例] 2 1 ※AtCoderのテストケースより [入力例] 2 1 2 1 2 3 2 2 6 [出力例] 0 ※AtCoderのテストケースより [入力例] 20 795629912 123625148 2 860243184 892786970 2 645778367 668513124 1 531411849 174630323 1 635062977 195695960 2 382061637 411843651 1 585964296 589553566 1 310118888 68936560 1 525351160 858166280 2 395304415 429823333 2 583145399 703645715 2 97768492 218377432 1 707220749 459967102 1 210842017 363390878 2 489541834 553583525 2 731279777 811513313 1 549864943 493384741 1 815378318 826084592 2 369622093 374205455 1 78240781 821999998 2 241667193 243982581 [出力例] 26468090 3491640 25280111 9543684 0 22804896 20649370 19245624 4849993 484865 ※AtCoderのテストケースより [入力例] 5 107 18 1 114 119 2 57 69 1 98 174 2 6 12 2 84 107 [出力例] 20 11 0 [入力例] 30 60894 114814 1 9771 9998 2 9658 10362 1 1365 13341 2 4171 13850 1 9150 11714 2 12131 14071 2 344 5388 1 5322 10266 2 4273 10731 2 11385 17232 1 10281 16940 1 6759 8420 1 5446 17385 2 6260 18019 1 4752 13325 2 10000 10097 1 7168 9965 2 6418 13448 1 2509 8811 1 10613 18269 2 8835 17767 2 1234 2345 1 7797 12603 2 6091 17241 1 9538 19041 1 6517 9903 2 4001 4119 1 5331 5746 2 2022 2023 2 10443 14634 [出力例] 9407 856 635 571 3975 0 0 4609 1258 0 1461 0 4228 2249 0 [入力例] 50 18589242 111515167 1 7857896 7870225 1 108996925 109007087 1 3231841 3240209 2 93037389 93041220 1 117002763 117005425 2 30927828 30938177 1 67763135 67763539 2 103805460 103806493 2 2567474 2573909 2 108020986 108023905 2 37217005 37225215 2 71809183 71809762 1 47840712 47847137 1 23141266 23150701 1 96045314 96056642 2 75122385 75129879 1 111472448 111479593 2 69249934 69255880 1 52940681 52948063 2 8747268 8748241 2 82901403 82910349 2 67133518 67139242 2 80698425 80703501 1 77496129 77504765 2 16477473 16489194 2 24902518 24903378 1 30300667 30307565 1 106636378 106640566 2 61268348 61273932 2 102619081 102619533 2 119718423 119724118 1 72829329 72839033 1 21800314 21802869 2 36235800 36238940 2 116969633 116981722 1 68026338 68031378 1 81596367 81597321 1 91644445 91646601 2 101519156 101529049 2 31970804 31976248 1 33941680 33942861 1 2973225 2980507 1 69937633 69948482 2 57466792 57470313 2 34804405 34808628 2 67101174 67108237 1 100202673 100211900 2 80333682 80345257 2 48041569 48048173 2 38853288 38857168 [出力例] 37063189 15199707 26297916 2567878 22080504 21488884 56081062 20557970 22957967 2275218 12777500 20841551 14984348 749352 9174397 660116 3269211 10380291 7364243 11080889 4359695 11626935 3137919 8794555 776304 12449141 1749602 4746015 |
■参照サイト
AtCoder Regular Contest 155