C++の練習を兼ねて, AtCoder Regular Contest 055 の 問題C (ABCAC) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, Z-Algorithm を, 復習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 055 解説 を ご覧下さい.
■C++版プログラム(問題C／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 |
// 解き直し. // https://img.atcoder.jp/data/arc/055/editorial.pdf // 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() int main(){ // 1. 入力情報. char c[202020]; scanf("%s", c); string S(c), R(c); int ss = S.size(); // 2. 反転. reverse(all(R)); // 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 p[202020], s[202020]; rep(i, 202020) p[i] = s[i] = 0; z(S, ss, p); z(R, ss, s); // 4. 全探索(ABC/AC). // ex. // x = aaaaababaab, y = aaaab // y の 分割 => x の 分割 を, それぞれ確認. // a/aaab => a/aaaaba/baab で, NG. // aa/aab => aa/aaabab/aab で, OK. // aaa/ab => aaa/aababa/ab で, OK. // aaaa/b => aaaa/ababaa/b で, OK. // -> OK は, 3個取れたので, 3通り. // -> この例では, prefix 4文字, suffix 3文字 まで 一致するので, // 4 + 3 - 5 (文字列 y のサイズ) + 1 = 3通り と 計算される. LL ans = 0; repx(i, ss / 2, ss - 2){ // 文字列 を 区間[0, i], [i + 1, ss - 1] に 分割し, 正当なものがいくつあるか？ int x = i + 1; int y = ss - i - 1; int a = p[x]; int c = s[y]; // 分割なし. if(a + c < y) continue; // 非空チェック. if(!a || !c) continue; // 分割あり. // ① 文字列 x の 分割(文字列 A (a文字), 文字列 B (1文字以上), 文字列 C (c文字)) は, 文字列 x の サイズ以下. // ② 文字列 y の 分割(文字列 A (a文字), 文字列 C (c文字)) は, 文字列 y の サイズ未満. // LL cur = (LL)min({x, a + c - y + 1, y - 1}); // 1_009.txt などで, WA版となったため, ロジック修正. // -> (a, c) の 組み合わせは, (1, y - 1), (2, y - 2), ..., (y - 1, 1) の 高々 (y - 1)個. // x > y の 範囲で考えているので, x については, 特に考慮する必要は無さそうに見える. // ③ (m, y - m) が, m <= a かつ y - m <= c となる 最大の m は？ // ④ (y - n, n) が, y - n <= a かつ n <= c となる 最大の n は？ LL m = (LL)max(min(a, y - 1), y - c); LL n = (LL)max(min(c, y - 1), y - a); LL cur = max(0LL, min(m + n - y + 1, (LL)(y - 1))); // 加算. ans += cur; } // 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 |
[入力例] takaitai [出力例] 2 ※AtCoderのテストケースより [入力例] aaaaaaaaaa [出力例] 6 ※AtCoderのテストケースより [入力例] abcabc [出力例] 0 ※AtCoderのテストケースより [入力例] aaaaa [出力例] 1 [入力例] abracadabra [出力例] 0 [入力例] aaaaabbbccccaaaccc [出力例] 1 [入力例] xyzxyzxyzxyzxyzxyzxyzxyzxyzxyz [出力例] 26 [入力例] aaaaabbbbcccaaaaabbbbcccaaaaabbbbcccdddaaaaabbbbcccddddaaaaabbbbcccdddddaaaaabbbbcccaaaaabbbbccc [出力例] 11 [入力例] aaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbccc [出力例] 86 [入力例] aabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbcccc [出力例] 316 |
■参照サイト
AtCoder Regular Contest 055