ABC 324
Table of Contents
https://atcoder.jp/contests/abc324
A. Same
https://atcoder.jp/contests/abc324/tasks/abc324_a
B. 3-smooth Numbers
https://atcoder.jp/contests/abc324/tasks/abc324_b
C. Error Correction
https://atcoder.jp/contests/abc324/tasks/abc324_c
D. Square Permutation
https://atcoder.jp/contests/abc324/tasks/abc324_d
E. Joint Two Strings
https://atcoder.jp/contests/abc324/tasks/abc324_e
$S_i$ の部分列と $T$ の prefix との共通部分の長さが $k$ となる $i$ の個数を $h_k$ とする。 同様に $S_i$ の部分列と $T$ の suffix との共通部分の長さが $k$ となる $i$ の個数を $t_k$ とする。
$T$ の prefix との共通部分の長さが $k$ となる文字には、$T$ の suffix との共通部分の長さが $N-k$ 以上となる文字を連結させれば $T$ を部分列として含むことができる。
よって求める個数は
\begin{align*} \sum_{k=0}^{N} \left\{ h_k \cdot \left( \sum_{j = N-k}^N t_{j} \right) \right\} \end{align*}
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
string T;
cin >> N >> T;
vector<string> S(N);
rep(i, N) cin >> S[i];
string revT = T;
reverse(all(revT));
vector<string> revS = S;
rep(i, N) reverse(all(revS[i]));
auto cal = [](vector<string> ss, string t) -> vll {
vll ret(t.size() + 1);
for (string s : ss) {
int i = 0;
for (char c : s) {
if (i >= (int)t.size())
break;
if (c == t[i])
i++;
}
ret[i]++;
}
return ret;
};
vll head = cal(S, T);
vll tail = cal(revS, revT);
int tsz = T.size();
fenwick_tree<ll> cumsum_tail(tsz + 1);
rep(i, tsz + 1) cumsum_tail.add(i, tail[i]);
ll ans = 0;
rep(i, tsz + 1) {
ans += head[i] * cumsum_tail.sum(tsz - i, tsz + 1);
}
cout << ans << endl;
}
F. Beautiful Path
https://atcoder.jp/contests/abc324/tasks/abc324_f