C++の練習を兼ねて, AtCoder Regular Contest 060 の 問題F (最良表現) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, Z-Algorithm を, 復習できたので, 非常に良かったと思う.
3. 解説のロジックで, 答えを見つけることが出来ることに, 非常に不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 060 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/data/arc/060/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--) #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. char c[505050]; scanf("%s", c); string w(c), rw(c); int ws = w.size(); // 2. (b) per(w) = 1. bool ok = true; rep(i, ws) if(w[0] != w[i]) ok = false; if(ok){ printf("%d\n%d\n", ws, 1); return 0; } // 3. 逆文字列. reverse(all(rw)); // 4. 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[505050], zb[505050]; rep(i, 505050) zf[i] = zb[i] = 0; z(w, ws, zf); z(rw, ws, zb); // 5. 配列 G. bool gf[505050], gb[505050]; rep(i, 505050) gf[i] = gb[i] = true; repx(p, 1, ws){ if(!gf[p]) continue; for(int k = 2; (k - 1) * p <= zf[p]; ++k) gf[k * p] = false; } repx(p, 1, ws){ if(!gb[p]) continue; for(int k = 2; (k - 1) * p <= zb[p]; ++k) gb[k * p] = false; } // 6. (a) w が 良い文字列. if(gf[ws]){ puts("1\n1"); return 0; } // 7. (c) それ以外. int ans = 0; repx(i, 1, ws) if(gf[i] && gb[ws - i]) ++ans; // 8. 出力. printf("%d\n%d\n", 2, 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 |
[入力例] aab [出力例] 1 1 ※AtCoderのテストケースより [入力例] bcbc [出力例] 2 3 ※AtCoderのテストケースより [入力例] ddd [出力例] 3 1 ※AtCoderのテストケースより [入力例] abbaabba [出力例] 2 7 [入力例] abracadabra [出力例] 1 1 [入力例] appleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppa [出力例] 2 90 [入力例] palindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilap [出力例] 2 950 [入力例] abcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacra [出力例] 2 1960 |
■参照サイト
AtCoder Regular Contest 060