C++の練習を兼ねて, AtCoder Beginner Contest 242 の 問題E ((∀x∀)) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, 回文の性質を学習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 242 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc242/editorial/3516 // 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() const LL MOD = 998244353; int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. 26進数(数え上げ, MOD版). auto f = [&](string s) -> LL{ LL ret = s.back() - 'A' + 1, d = 1; s.pop_back(); for(auto i = s.rbegin(), e = s.rend(); i != e; ++i){ d *= 26; d %= MOD; ret += d * (*i - 'A'); ret %= MOD; } return ret; }; // 3. 各テストケース. rep(i, T){ // 3-1. テストケース入力情報. int N; scanf("%d", &N); char c[N + 2]; scanf("%s", c); string s(c); // 3-2. 争点以下の回文は? int l = N / 2 + (N & 1); // 3-3. 数え上げ. string ls1 = s.substr(0, l); string ls2 = s.substr(0, l); LL ans = f(ls1); // 3-4. 争点を含むか? if(N & 1) ls2.pop_back(); reverse(all(ls2)); bool ok = (s >= (ls1 + ls2)); // 3-5. 調整. if(!ok) ans = (ans + MOD - 1) % MOD; // 3-6. 出力. printf("%lld\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 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 |
[入力例] 5 3 AXA 6 ABCZAZ 30 QWERTYUIOPASDFGHJKLZXCVBNMQWER 28 JVIISNEOXHSNEAAENSHXOENSIIVJ 31 KVOHEEMSOZZASHENDIGOJRTJVMVSDWW [出力例] 24 29 212370247 36523399 231364016 ※AtCoderのテストケースより [入力例] 15 1 Y 2 QV 3 WUB 4 EMLO 5 BRPYK 6 IOGENQ 7 GFVUUCZ 8 ZIVJKEYM 9 NDBSFVDYH 10 WZQZSCRLDQ 11 VJIXLFEULDB 12 DPFUNZWSZJGH 13 DCLBLJYXTODNY 14 BJZDDURALFRQKL 15 OBWIJRFKQCBOQJL [出力例] 25 17 592 116 1134 5778 109402 445364 5994566 10504356 253778127 42600531 955562087 427327853 217862248 [入力例] 25 1 L 2 HY 3 YND 4 PBWS 5 ORNNI 6 IFNVBT 7 WJISVPH 8 EEDSQXLZ 9 DKAERSRFW 10 VPGHNOIXIA 11 CNGTEXXGTIZ 12 ZGOXEITISMBT 13 ZLZJBWQIWYBTP 14 BJZVLXZESZXWEB 15 LXTXUWGAHXRHXTA 16 VBJSDIVMYNAQMKEN 17 DVXDPPOHTLUBKFFKA 18 FTUURWFXQTDVJCVVMG 19 NMETRNMBEBQCFYYIGTN 20 ZOYRRWYQZETEGCQSFMEY 21 KBLMLWYCQVMDABYYHMYLC 22 TESOQWGINVBEZRSSOUAMMH 23 KHRNAOXSBCXIULNBGKIUTRR 24 THEQLJFLISRSERNCELIYORZP 25 WBDHWUJPAYTVWEOMDLGOAKHPB [出力例] 12 8 637 392 9919 5552 392983 73104 1546810 9864388 29821868 300037981 877462913 427649715 858384390 388850462 706826887 279373158 289054454 614125680 129623060 618481925 127581610 608225133 666465408 |
■参照サイト
AtCoder Beginner Contest 242