C++の練習を兼ねて, AtCoder Beginner Contest 324 の 問題E (Joint Two Strings) を解いてみた.
■感想.
1. 問題Eは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題E で, 二分探索の復習が出来たので, 良かったとおもう.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 324 解説 の 各リンク を ご覧下さい.
■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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
// C++20(GCC 12.2) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using vvi = vector<vi>; 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 #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; char t[505050]; scanf("%d %s", &N, t); int ts = strlen(t); vs v; rep(i, N){ string s; cin >> s; v.pb(s); } // 2. 文字列 T と, 何文字一致するか？ vi lCount, rCount; for(auto &s : v){ // 文字列 S の 各文字の出現位置は？ vvi idxs(26); rep(i, s.size()) idxs[s[i] - 'a'].pb(i); // 左から数える場合. int idx = -1, c = 0; rep(i, ts){ int cur = t[i] - 'a'; if(!idxs[cur].size()) break; int at = upper_bound(all(idxs[cur]), idx) - idxs[cur].begin(); if(at == idxs[cur].size()) break; if(idx >= idxs[cur][at]) break; idx = idxs[cur][at]; ++c; } lCount.pb(c); // 右から数える場合. idx = s.size(), c = 0; repr(i, ts - 1, 0){ int cur = t[i] - 'a'; if(!idxs[cur].size()) break; int at = lower_bound(all(idxs[cur]), idx) - idxs[cur].begin(); if(!at && idx <= idxs[cur][at]) break; idx = idxs[cur][max(0, at - 1)]; ++c; } rCount.pb(c); } // 3. sort. sort(all(lCount)); sort(all(rCount)); // 4. 集計. LL ans = 0; for(auto &l : lCount){ int at = lower_bound(all(rCount), ts - l) - rCount.begin(); ans += (LL)(rCount.size() - at); } // 5. 出力. 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 |
[入力例] 3 bac abba bcb aaca [出力例] 3 ※AtCoderテストケースより [入力例] 5 xx x x x x x [出力例] 25 ※AtCoderテストケースより [入力例] 10 ms mkgn m hlms vmsle mxsm nnzdhi umsavxlb ffnsybomr yvmm naouel [出力例] 68 ※AtCoderテストケースより [入力例] 3 a a a a [出力例] 9 [入力例] 5 pqr smcmwubocdxvlifbvncjmvrpyq mhjzknucbwjyprclfyhlgrmhgp vhmdqgdikfooemfqlgkeocqntw uglthudqauvtlnvztvtopvukbr xmdthyfzaeubkdmjapnplgnyyf [出力例] 6 [入力例] 10 atcoder swlazbtdveckiojddjvezrrsjzimjjog noajutwvbcmuzoswnctqobguletpsq xcfgesaszjcpetuyxufehuiffg tkrvoawtwcyizodxbdwxeecrrdiadeezrckw forgemtxmwnblzyhzpsjrcynhx dkaawtxfkciqkogptdjzblukvgpqjn pttmiajkmezpmmvyrdujkeqerynzm dplzhanztxxcfoozvadexeiprlzrlklyui qskedvmgavbtfdvcmecwerwjwgqoch ditpzonoidultevbrzsddrueqarysfcbt [出力例] 61 [入力例] 30 abracadabra frlhabracacdavbacadyjotqfiajpfrsfalqmpqzm pnsabraaasbboigplsbkqaytpztlty dabrarenuxjbnmwejvumayzqmjacadyueir vrafdksqwxwphvbabracxadyaubraxsnhiyimkgj vopsvoomcfekesrqblqxjacaderhok hephqdabrahgabrailbwcnykgnueerasxlz dfdoqdncuaybkxabracxmzgjnmtkioc apbiybracaudabirglrzehsfuhrhuoczuduwb ruxxacadfdcacadizqzeefryriesteziip xzqjtdewrnyabraquyjhabracaidabirayberuirmjf hafudwmabracadabrampgdabraurlmyacdayrmezgrnkd ccamcpjhmcinhabracadabrauubcytmtoyksr rtgpyiaqqcthxabracadadbrdaduhazyiintogf nciseywsrseoyiodabraskzmabraqsmknfc qabracaydaubrasgnjpsyonenfehongsupwralz xdsbjgybfbmiabraicaodabrayeetrlzqyikhxv wopsvxldeemevmebagfmdabratnnabraodq ccdsyjhxfmvltkgvdxdacadfzijmtk pjrxhwalfpetfydzcabracieagtvswdabrah egvbabacadaebrcrzxhqsxpxglqucndgzllk wlpdpbvlhrleulaoahghgjlacadddz qebhqkeksdiviwwabracadabrarvhwxlizrjx vzifenabrabznwcwkcdblrwxbbzdabrajks lpepabjpuxabrarhupexbcwivbapol dwomabracaudaobrargvgrkfpodelkgzntgszzr qwvbgaivdyummkaraptmdabrablkecktwm ytguxctdeoclbpacadzybhumyzlxjo ykxggshcsuxutqbupmqzpscrgdabrag gixkvjvuimdfgmttdhabatinoxmbp pzslmvoulsgxnxocjgmifdabraqfxym [出力例] 606 |
■参照サイト
日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324）