C++の練習を兼ねて, AtCoder Beginner Contest 138 の 問題E (E – Strings of Impurity) を解いてみた.
■感想.
1. 複雑なロジックとなったが, なんとか実装できた.
2. TLE版 を 解消して, AC版に到達出来た.
※ TLE版 にあるように, for文内で, vector の 変数宣言することが, 非常に重たい処理であることが分かり, 勉強になった.
3. 苦手なdpの訓練を積めたので良かったと思う.
本家のサイトABC 138解説をご覧下さい.
■C++版プログラム(問題E／TLE版).
|
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 |
// b10, b14, b15 で, TLE と なった. #include <bits/stdc++.h> using namespace std; using LL = long long; const string ALPHABET = "abcdefghijklmnopqrstuvwxyz"; // 文字列 T の 先頭から, 順に, 文字列 S を 1グーゴル個連結した文字列(以下, S'と略記)中に, 出現する位置 を 保存. LL dp[111111]; // 文字列 S の 各文字 の 出現位置 を 保管. vector<vector<LL>> sPos(26); int main(){ // 1. 入力情報取得. char S[111111], T[111111]; scanf("%s %s", S, T); int sl = strlen(S); int tl = strlen(T); // 2. 各文字の出現回数を保存. map<char, int> ms, mt; for(int i = 0; i < ALPHABET.size(); i++) ms[ALPHABET[i]] = 0, mt[ALPHABET[i]] = 0; for(int i = 0; i < sl; i++){ ms[S[i]]++; int index = S[i] - 'a'; sPos[index].push_back(i + 1); } for(int i = 0; i < tl; i++) mt[T[i]]++; // for(int i = 0; i < 26; i++){ // for(auto &p : sPos[i]) printf("%lld ", p); // printf("\n"); // } // 3. 存在しないケースを出力. // 文字列 S に 存在しない文字が, 文字列 T に 含まれている場合. for(auto &p : mt){ char c = p.first; if(ms[c] == 0 && mt[c] > 0){ printf("%d\n", -1); return 0; } } // 4. dp更新. // ex. // S = contest // T = sentence // -> 以下のように考える. // 文字列 T の 各文字 について, 文字列 S で, 何番目 を 使っているか見る. // s: 6 // e: 5 -> 12 // n: 3 -> 10 -> 17 // t: 4 -> 7 -> 11 -> 14 -> 18 // e: 5 -> 12 -> 19 // n: 3 -> 10 -> 17 -> 24 // c: 1 -> 8 -> 15 -> 22 -> 29 // e: 5 -> 12 -> 19 -> 26 -> 33 // -> 上記から, 33文字 と 判明. LL bef = 0; // 前回出現位置. for(int i = 0; i < tl; i++){ // 今回チェックする文字列 T 中 の 文字 c. char c = T[i]; int index = c - 'a'; // 文字列 S 中 の 文字 c に関する出現位置情報. vector<LL> p = sPos[index]; // 今回出現位置 は 前回出現位置 から 逆算. LL tmp = lower_bound(p.begin(), p.end(), (bef % sl + 1)) - p.begin(); LL cPos = 0; if(tmp == p.size()) cPos = (bef / sl + 1) * sl + p[0]; // 末尾なら, 次のサイクルの最初の要素を設定. else cPos = (bef / sl) * sl + p[tmp]; // 上記までで計算した位置を元に, dp を 更新. dp[i] = cPos; // 前回情報更新. bef = cPos; } // 5. 出力 ～ 後処理. // for(int i = 0; i < tl; i++) printf("%lld ", dp[i]); // printf("\n"); printf("%lld\n", dp[tl - 1]); return 0; } |
■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 78 79 80 81 82 83 |
#include <bits/stdc++.h> using namespace std; using LL = long long; const string ALPHABET = "abcdefghijklmnopqrstuvwxyz"; // 文字列 T の 先頭から, 順に, 文字列 S を 1グーゴル個連結した文字列(以下, S'と略記)中に, 出現する位置 を 保存. LL dp[111111]; // 文字列 S の 各文字 の 出現位置 を 保管. vector<vector<LL>> sPos(26); int main(){ // 1. 入力情報取得. char S[111111], T[111111]; scanf("%s %s", S, T); int sl = strlen(S); int tl = strlen(T); // 2. 各文字の出現回数を保存. map<char, int> ms, mt; for(int i = 0; i < ALPHABET.size(); i++) ms[ALPHABET[i]] = 0, mt[ALPHABET[i]] = 0; for(int i = 0; i < sl; i++){ ms[S[i]]++; int index = S[i] - 'a'; sPos[index].push_back(i + 1); } for(int i = 0; i < tl; i++) mt[T[i]]++; // for(int i = 0; i < 26; i++){ // for(auto &p : sPos[i]) printf("%lld ", p); // printf("\n"); // } // 3. 存在しないケースを出力. // 文字列 S に 存在しない文字が, 文字列 T に 含まれている場合. for(auto &p : mt){ char c = p.first; if(ms[c] == 0 && mt[c] > 0){ printf("%d\n", -1); return 0; } } // 4. dp更新. // ex. // S = contest // T = sentence // -> 以下のように考える. // 文字列 T の 各文字 について, 文字列 S で, 何番目 を 使っているか見る. // s: 6 // e: 5 -> 12 // n: 3 -> 10 -> 17 // t: 4 -> 7 -> 11 -> 14 -> 18 // e: 5 -> 12 -> 19 // n: 3 -> 10 -> 17 -> 24 // c: 1 -> 8 -> 15 -> 22 -> 29 // e: 5 -> 12 -> 19 -> 26 -> 33 // -> 上記から, 33文字 と 判明. LL bef = 0; // 前回出現位置. for(int i = 0; i < tl; i++){ // 今回チェックする文字列 T 中 の 文字 c. char c = T[i]; int index = c - 'a'; // 文字列 S 中 の 文字 c に関する出現位置情報 … sPos[index]. // 今回出現位置 は 前回出現位置 から 逆算. LL tmp = lower_bound(sPos[index].begin(), sPos[index].end(), (bef % sl + 1)) - sPos[index].begin(); LL cPos = 0; if(tmp == sPos[index].size()) cPos = (bef / sl + 1) * sl + sPos[index][0]; // 末尾なら, 次のサイクルの最初の要素を設定. else cPos = (bef / sl) * sl + sPos[index][tmp]; // 上記までで計算した位置を元に, dp を 更新. dp[i] = cPos; // 前回情報更新. bef = cPos; } // 5. 出力 ～ 後処理. // for(int i = 0; i < tl; i++) printf("%lld ", dp[i]); // printf("\n"); printf("%lld\n", dp[tl - 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 |
[入力例] contest son [出力例(debug版)] 6 9 10 10 ※AtCoderテストケースより [入力例] contest programming [出力例(debug版)] -1 ※AtCoderテストケースより [入力例] contest sentence [出力例(debug版)] 6 12 17 18 19 24 29 33 33 ※AtCoderテストケースより [入力例] aiueo aiueo [出力例(debug版)] 1 2 3 4 5 5 [入力例] jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoronisumutokoroyaburakojinoburakojipaipopaipopaiponoshuringanshuringannogurindaigurindainopompokopinopompokonanochokyumeinochosukezyugemuzyugemugokonosurikirekaizyarisuigyonosuigyomatuunraimatuhuraimatukuunerutokoronisumutokorol magicalspell [出力例(debug版)] 5 28 37 44 194 241 309 328 426 510 618 927 927 |
■参照サイト
AtCoder Beginner Contest 138