Codeforces Round #556 (Div. 2) D. Three Religions

解法

まずクエリが存在しない場合にどのように解くか考える。構造が複雑で制約も小さいのでdpをする。 $dp \lbrack i \rbrack\lbrack x \rbrack \lbrack y \rbrack \lbrack z \rbrack =$ 文字列 $s$ の $i$ 番目までで(文字列1の $x$ 文字 && 文字列2の $y$ 文字 && 文字列3の $z$ 文字)をつくれるか? という愚直なdpがあるがこのままでは状態数が大きすぎてTLEする。dpの値がtrue/falseの2択になっているがここに情報を持たせる。 $dp \lbrack x \rbrack \lbrack y \rbrack \lbrack z \rbrack =$ 文字列 $s$ の何番目まででつくれるか? としたdpが可能である。dpの遷移は
$dp \lbrack x \rbrack \lbrack y \rbrack \lbrack z \rbrack = \min ($ 文字列 $s$ の $dp \lbrack x-1 \rbrack \lbrack y \rbrack \lbrack z \rbrack$ より後で文字列1の $x$ 文字目が現れる最初の位置, 文字列 $s$ の $dp \lbrack x \rbrack \lbrack y-1 \rbrack \lbrack z \rbrack$ より後で文字列2の $y$ 文字目が現れる最初の位置, 文字列 $s$ の $dp \lbrack x \rbrack \lbrack y \rbrack \lbrack z-1 \rbrack$ より後で文字列3の $z$ 文字目が現れる最初の位置 $)$
となる。文字列 $s$ で $i$ 文字目以降で文字 $c$ が現れる最初の位置を前計算しておくことでこれらの遷移は $O(1)$ で計算できる。よってクエリが存在しない場合の計算量は $250^{3}$ 程度でできる。
クエリごとに毎回dpをしていたのでは $1000 \times 250^{3}$ かかってしまいTLEする。クエリで変化するのは文字列の末尾1文字だけである点に注目する。クエリによって文字列1の長さが変化したとする。このときdpの値が変動する場所は $dp \lbrack$ 文字列1の長さ $\rbrack \lbrack y \rbrack \lbrack z \rbrack$ だけであり $250^{2}$ 個しか変動しないことがわかる。その他の文字列の長さが変化したとしても同様に $250^{2}$ 個しか変動しないため $1000\times 250^{2}$ 程度の計算量で問題なく解けることがわかる。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

ll dp[255][255][255], pos[100010][30];
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    FOR(j, n-1, 100010) REP(i, 26) pos[j][i] = INF;
    for(ll i=n-1; i>=0; --i) {
        REP(j, 26) {
            if(j == s[i]-'a') pos[i][j] = i;
            else if(i<n-1) pos[i][j] = pos[i+1][j];
        }
    }

    REP(i, 255) REP(j, 255) REP(k, 255) dp[i][j][k] = INF;
    dp[0][0][0] = -1;

    vector<string> v(3);
    while(q--) {
        char type;
        cin >> type;
        if(type == '+') {
            ll idx;
            char c;
            cin >> idx >> c;
            idx--;
            v[idx] += c;
            ll a, b;
            if(idx == 0) a = 1, b = 2;
            else if(idx == 1) a = 0, b = 2;
            else if(idx == 2) a = 0, b = 1;
            REP(i, v[a].size()+1) REP(j, v[b].size()+1) {
                ll x=-1, y=-1, z=-1;
                if(idx == 0) x = v[0].size(), y = i, z = j;
                else if(idx == 1) x = i, y = v[1].size(), z = j;
                else if(idx == 2) x = i, y = j, z = v[2].size();

                if(x) {
                    ll tmp = dp[x-1][y][z]+1;
                    if(tmp < n) chmin(dp[x][y][z], pos[tmp][v[0][x-1]-'a']);
                }
                if(y) {
                    ll tmp = dp[x][y-1][z]+1;
                    if(tmp < n) chmin(dp[x][y][z], pos[tmp][v[1][y-1]-'a']);
                }
                if(z) {
                    ll tmp = dp[x][y][z-1]+1;
                    if(tmp < n) chmin(dp[x][y][z], pos[tmp][v[2][z-1]-'a']);
                }
            }
        } else {
            ll idx;
            cin >> idx;
            idx--;

            if(idx == 0) {
                REP(i, v[1].size()+1) REP(j, v[2].size()+1) {
                    dp[v[0].size()][i][j] = INF;
                }
            } else if(idx == 1) {
                REP(i, v[0].size()+1) REP(j, v[2].size()+1) {
                    dp[i][v[1].size()][j] = INF;
                }
            } else if(idx == 2) {
                REP(i, v[0].size()+1) REP(j, v[1].size()+1) {
                    dp[i][j][v[2].size()] = INF;
                }
            }
            v[idx].pop_back();
        }

        if(dp[v[0].size()][v[1].size()][v[2].size()] < n) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

ferinの競プロ帳

競プロについてのメモ

Codeforces Round #556 (Div. 2) D. Three Religions

解法