C++の練習を兼ねて, AtCoder Beginner Contest 257 の 問題G (Prefix Concatenation) を解いてみた.
■感想.
1. 問題Gは, 方針が見えなかったので, 解説プログラムを参考に, AC版に到達できたと思う.
2. 新しい知識として, Z-Algorithm を, 学習できたので, 非常に良かったと思う.
3. 苦手な動的計画法の訓練も積めたので, 非常に良かったと思う.
4. S = abcabc の 場合, f[i] = 6 0 0 3 2 1 に変えて, f[i] = 6 0 0 3 0 0 が正しい結果に見えるため, Z-Algorithm の 実装箇所から, 以下の部分を削除し, 再提出した.
|
1 2 3 4 |
if(r == ss){ f[i] = ss - i; continue; } |
5. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 257 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題G／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 |
// 解答不能. // https://atcoder.jp/contests/abc257/editorial/4185 // 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 s[505050], t[505050]; scanf("%s %s", s, t); string S(s), T(t); int ss = S.size(); int ts = T.size(); // 2. Z-Algorithm. // https://atcoder.jp/contests/abc257/editorial/4185 // -> 解説プログラム一部変更. // ex. // S = aaabbcddaaabbaaaeaaabbcaaabbcddaaabbaefgaaabbcdaaa の 場合, // f[i] = 50 2 1 0 0 0 0 0 5 2 1 0 0 3 2 1 0 6 2 1 0 0 0 14 2 1 0 0 0 0 0 5 2 1 0 0 1 0 0 0 7 2 1 0 0 0 0 3 2 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 f[505050]; rep(i, 505050) f[i] = 0; z(s, ss, f); // 3. dp更新. // -> 解説の文章で説明されている添え字の対応関係が, 不明だったため, 解説プログラムを一部修正して提出. int dp[505050]; rep(i, 505050) dp[i] = -1; int l = 0, r = 0; rep(i, ts){ if(r == ts) break; if(!i){ rep(j, min(ss, ts)){ if(S[j] != T[j]) break; dp[j] = 1; r = j + 1; } continue; } if(dp[i - 1] == -1) break; if(f[i - l] >= r - i){ while(r < ts && (r - i) < ss){ if(T[r] != S[r - i]) break; dp[r] = dp[i - 1] + 1; ++r; } l = i; } } // 4. 出力. printf("%d\n", dp[ts - 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 42 43 |
[入力例] aba ababaab [出力例] 3 ※AtCoderテストケースより [入力例] atcoder ac [出力例] -1 ※AtCoderテストケースより [入力例] abcab aaabb [出力例] -1 [入力例] abcab aabaaababcababc [出力例] 7 [入力例] aaabbcddaaabbaaaeaaabbcaaabbcddaaabbaefgaaabbcdaaa aaaaaaaaaaaaaaaaaaaabbcddaaabbaaaeaaabbcaaabbcddaaabbaaaeaaabbcaaaaaabbcddaaabbaaaeaaabbcaaabbcddaaabbaef [出力例] 9 [入力例] abcopq abcopqaabcopqaaabcopqaaaabcopqaaaaabcopqaaaaaabcopqaaaaaaabcopqaaaaaaaabcopqaaaaaaaaabcopqaaaaaaaaaabcopq [出力例] 55 |
■参照サイト
日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257）