ABC 284
Table of Contents
https://atcoder.jp/contests/abc284
A. Sequence of Strings
https://atcoder.jp/contests/abc284/tasks/abc284_a
B. Multi Test Cases
https://atcoder.jp/contests/abc284/tasks/abc284_b
C. Count Connected Components
https://atcoder.jp/contests/abc284/tasks/abc284_c
D. Happy New Year 2023
https://atcoder.jp/contests/abc284/tasks/abc284_d
E. Count Simple Paths
https://atcoder.jp/contests/abc284/tasks/abc284_e
F. ABCBAC
https://atcoder.jp/contests/abc284/tasks/abc284_f
2026/2/9 Z Algorithm 解法
$S$ の前半 $i$ 文字を ${\color{red}\rightarrow}$、後半 $i$ 文字を ${\color{blue}\Rightarrow}$ とする。 すなわち $S = {\color{red}\rightarrow} {\color{blue}\Rightarrow}$ である。
そうすると $T = {\color{red}\rightarrow} {\color{blue}\Leftarrow} {\color{red}\leftarrow} {\color{blue}\Rightarrow}$ となる。
前半 $N$ 文字を $L$, 後半 $N$ 文字を $R$ とする。 $L = {\color{red}\rightarrow} {\color{blue}\Leftarrow}$, $R = {\color{red}\leftarrow} {\color{blue}\Rightarrow}$.
$A = L + revR = {\color{red}\rightarrow} {\color{blue}\Leftarrow} {\color{blue}\Leftarrow} {\color{red}\rightarrow}$, $B = revR + L = {\color{blue}\Leftarrow} {\color{red}\rightarrow} {\color{red}\rightarrow} {\color{blue}\Leftarrow}$ とする。
$A, B$ の Z Algorithm も求めて共通接頭辞の長さを調べて $i$ を求めれば良い。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
string T;
cin >> N >> T;
string t1 = T.substr(0, N);
string t2 = T.substr(N, N);
reverse(all(t2));
vint za = z_algorithm(t1 + t2);
vint zb = z_algorithm(t2 + t1);
rep(i, N) {
if (i && za[N * 2 - i] != i) continue;
ll j = N - i;
if (zb[N + i] != j) continue;
string s = t1 + t2;
string ans = s.substr(0, i);
string b = s.substr(N, j);
reverse(all(b));
ans += b;
cout << ans << endl;
cout << i << endl;
return;
}
cout << -1 << endl;
}
2026/2/6 Rolling Hash 解法
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
string T;
cin >> N >> T;
vector<mint> pows(N);
mint m = 998244353;
pows[0] = 1;
rep2(i, 1, N) pows[i] = pows[i - 1] * m;
mint left = 0, right = 0;
rep(i, N) {
left *= m;
left += T[i];
right *= m;
right += T[N * 2 - 1 - i];
}
string ans = "-1";
int num = 0;
rep(i, N + 1) {
if (left == right) {
string r = T.substr(N - i, N);
string l = T.substr(0, N - i) + T.substr(N * 2 - i, i);
reverse(all(r));
if (r == l) {
ans = r;
num = N - i;
break;
}
}
if (i == N) break;
char c1 = T[N - 1 - i], c2 = T[N * 2 - 1 - i];
left -= c1 * pows[i];
left += c2 * pows[i];
right -= c2 * pows[N - 1];
right *= m;
right += c1;
}
if (ans == "-1") {
cout << -1 << endl;
return;
}
cout << ans << endl;
cout << num << endl;
}
G. Only Once
https://atcoder.jp/contests/abc284/tasks/abc284_g