ABC324-Eを解いてみた

問題へのリンク
考察
1. Step1: 累積和を求める
2. Step2: 各Siについての通り数を累積和を使って高速に求める
ACしたコード

問題へのリンク

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

考察

Step1: 累積和を求める

以下、この記事では
“部分列” :=連続とは限らない部分列
|?| :=?の文字数
という意味で呼ぶことにする

まず制約が 1<=n<=5 * 10⁵ と大きいことからN²通りを全探索することはできないと分かる

ここで、問題の条件を少し言い換える事を考えてみる。
“Si と Sj をこの順に連結して得られる文字列は、T を(連続とは限らない)部分列として含む。
これは、
“「Si が Tの前側x文字を部分列として含む」
かつ
「SjがTの後ろ側|T| – x文字以上を部分列として含む」“
と言い換えられる

この言い換えにより
「SjがTの後ろ側|T| – x文字以上を部分列として含む」ようなSjの数を予め求めておけば
各Siに対しての通り数を高速に求められる
(つまり、全ての文字列とtを後ろから見ていった時に、各文字列に対して何個一致させられたかをメモしていく
詳しくはコード例のstep:1をみてね～)
注意点として、x文字“以上”を含むものの数が知りたいので一致させられた個数が多い方から累積和をとっておきます

//step1:
//can_create_cum[i]:= tの後ろからi文字目以上作れるものの数
vector<ll> can_create_cum(MAX_LENGTH + 1, 0);

//各文字列について、{各文字列,t}の後ろから順に部分文字列を作っていった時の作れる文字数を調べる
string rev_t = t;
ranges::reverse(rev_t);

for (int i = 0; i < n; i++) {
    int s_length = string_vec[i].size();
    string rev_s = string_vec[i];
    ranges::reverse(rev_s);

    int can_create_count = 0;
    //後ろから(逆順での前から) 作れる文字数を調べる
    for (int j = 0; j < s_length; j++) {
        if (rev_s[j] == rev_t[can_create_count]) can_create_count++;
        //tについて見終えたので抜ける
        if (can_create_count == t_length) break;
    }
    can_create_cum[can_create_count]++;
}

//i文字目"以上"作れるものが欲しいので後ろから累積和をとる
for (int i = MAX_LENGTH - 1; i >= 0; i--) can_create_cum[i] += can_create_cum[i + 1];

Step2: 各Siについての通り数を累積和を使って高速に求める

累積和を取った後は各文字列をSiとして選んだ場合の通り数を答えに加算していくだけです

//step2:
ll ans = 0;
//各文字列について、{各文字列, t}を前から順に部分文字列を作っていった時の作れる文字数を調べる。
//そのとき、can_create_cum[t.size() - "前側で作れた数"]を答えに加算する
for (int i = 0; i < n; i++) {
    int s_length = string_vec[i].size();
    string s = string_vec[i];
    int can_create_count = 0;
    for (int j = 0; j < s_length; j++) {
        if (s[j] == t[can_create_count]) can_create_count++;
        //tについて見終えたので抜ける
        if (can_create_count == t_length) break;
    }
    
    ans += can_create_cum[t_length - can_create_count];
}

ACしたコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MAX_LENGTH = 1e5 * 5;

int main() {
    int n;
    string t;
    cin >> n >> t;
    vector<string> string_vec(n);
    for (int i = 0; i < n; i++) cin >> string_vec[i];

    int t_length = t.size();

    //step1:
    //can_create_cum[i]:= tの後ろからi文字目以上作れるものの数
    vector<ll> can_create_cum(MAX_LENGTH + 1, 0);

    //各文字列について、{各文字列,t}の後ろから順に部分文字列を作っていった時の作れる文字数を調べる
    string rev_t = t;
    ranges::reverse(rev_t);
    for (int i = 0; i < n; i++) {
        int s_length = string_vec[i].size();
        string rev_s = string_vec[i];
        ranges::reverse(rev_s);

        int can_create_count = 0;
        //後ろから(逆順での前から) 作れる文字数を調べる
        for (int j = 0; j < s_length; j++) {
            if (rev_s[j] == rev_t[can_create_count]) can_create_count++;
            //tについて見終えたので抜ける
            if (can_create_count == t_length) break;
        }
        can_create_cum[can_create_count]++;
    }
    //i文字目"以上"作れるものが欲しいので後ろから累積和をとる
    for (int i = MAX_LENGTH - 1; i >= 0; i--) can_create_cum[i] += can_create_cum[i + 1];


    //step2:
    ll ans = 0;
    //各文字列について、{各文字列, t}を前から順に部分文字列を作っていった時の作れる文字数を調べる。
    //そのとき、can_create_cum[t.size() - "前側で作れた数"]を答えに加算する
    for (int i = 0; i < n; i++) {
        int s_length = string_vec[i].size();
        string s = string_vec[i];
        int can_create_count = 0;
        for (int j = 0; j < s_length; j++) {
            if (s[j] == t[can_create_count]) can_create_count++;
            //tについて見終えたので抜ける
            if (can_create_count == t_length) break;
        }
        
        ans += can_create_cum[t_length - can_create_count];
    }

    cout << ans;
}