C++の練習を兼ねて, AtCoder Beginner Contest 135 の 問題F (Strings of Eternity) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, Z-Algorithm を, 復習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 135 解説 を ご覧下さい.
■C++版プログラム(問題F／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 101 102 103 104 105 106 107 108 109 110 |
// 解き直し. // https://img.atcoder.jp/abc135/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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. 入力情報. char c1[505050], c2[505050]; scanf("%s %s", c1, c2); string s(c1), t(c2); int ss = s.size(); int ts = t.size(); // 2. 文字列 s の 拡張. string es = t + s + s; while(es.size() < 3 * ts) es += s; int ess = es.size(); // 3. Z-Algorithm. // https://atcoder.jp/contests/abc257/editorial/4185 // -> 解説プログラム一部変更. // ex. // S = abracadabra の 場合, // f[i] = 11 0 0 1 0 1 0 4 0 0 1 // // S = abcabc の 場合, // f[i] = 6 0 0 3 0 0 auto z = [](string s, int ss, int* f){ int l = 0, r = 1; f[0] = ss; repx(i, 1, ss){ if(i > 1 && f[i - l] < r - i){ f[i] = f[i - l]; continue; } r = max(i, r); while(r < ss){ if(s[r] == s[r - i]) ++r; else break; } f[i] = r - i; l = i; } }; int zf[ess]; rep(i, ess) zf[i] = 0; z(es, ess, zf); // rep(i, ess) printf("%d ", zf[i]); // puts(""); // 4. match設定. bool m[ss]; rep(i, ss) m[i] = 0; rep(i, ss) if(zf[i + ts] >= ts) m[i] = true; // 5. 有向グラフ作成. int p[ss], iDegree[ss], oDegree[ss]; rep(i, ss){ p[i] = -1; iDegree[i] = oDegree[i] = 0; } rep(i, ss){ if(m[i]){ int j = (i + ts) % ss; p[j] = i; ++iDegree[j]; ++oDegree[i]; } } // 6. 例外(ループあり). // -> 入次数: 1, 出次数: 1 の 頂点 が 1 個以上あって, // それ以外は, 入次数: 0, 出次数: 0 の 頂点 で構成される場合. int d00 = 0, d11 = 0; rep(i, ss){ if(!iDegree[i] && !oDegree[i]) ++d00; if(iDegree[i] && oDegree[i]) ++d11; } if(d11 >= 1 && d00 + d11 == ss){ puts("-1"); return 0; } // 7. ループなし. int ans = 0; rep(i, ss){ if(iDegree[i] && !oDegree[i]){ // 最長パス候補は？ int cur = i, d = 0; while(p[cur] != -1){ cur = p[cur]; ++d; } // 最大値更新. ans = max(ans, d); } } // 8. 出力. printf("%d\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 |
[入力例] abcabab ab [出力例] 3 ※AtCoderのテストケースより [入力例] aa aaaaaaa [出力例] -1 ※AtCoderのテストケースより [入力例] aba baaab [出力例] 0 ※AtCoderのテストケースより [入力例] ab baba [出力例] -1 [入力例] pqr pqr [出力例] -1 [入力例] abccabababcab ab [出力例] 3 [入力例] pqryulzmwlyuqypqrzznspqrpqrpqrpqr pqr [出力例] 5 [入力例] dpdpdpdpdpddddpdpddddpdpdddppddpdpddppdppddpddpdpdpdpdpdpddpppdpppddpdddppddppppddddppddppddpppddpdp dp [出力例] 7 [入力例] deratcoderatcoderatcoderatcoderatcoderatcoderatcoderatcoderfqeluoqgtgfrdknbkruhnpglwoxfaesjqtobfwyiacxitikrlgbpedkofbabheyigovkybvygeatqyeisjzvjkgxfwvafkyledxiutjmedatcoderwznatcoderatcodervvtgcryerfpbzwwfaqksxxiepjtkjugzyfthzxexzehfxlqlvnbirejatqksjqztrpzamynpxavqlqkvsbwyamkxavdquqrgsuvatcoderatcoderatcoderatcoderatcoderonyhvvgyqmkskoxzwrdrcvuhpoyuwykplwomgnebqhthylhkxocfrbcgufzlyywpviqkqmofctqwmdhzmbnaqwpjehlkwaezntcqsfwbctagjuldzrmpzfylcezxdqdmasjluzexjfmjxetfbnxacewpcwlhsuoqjszkokatcoderatco atcoder [出力例] 10 |
■参照サイト
AtCoder Beginner Contest 135