Three Religions [Codeforces Round #556 (Div. 1) B]

https://codeforces.com/contest/1149/problem/B

N文字の文字列Sがある。
3つの文字列スタックがある。
これに対してQ回以下のクエリを行う。

1. 「+ i c」i番目の文字列キューの末尾にcを入れる
2. 「- i」i番目の文字列キューの末尾をpopする

各クエリ後に以下の条件を満たすか答えよ。

3つの文字列スタックを独立した部分文字列として文字列Sが持つか。
それぞれの部分文字列は連続でなくてもいいが、順番は保つ必要がある。

1≦N≦10^5
1≦Q≦10^3
各文字列スタックの最大は250

解説

https://codeforces.com/contest/1149/submission/53520032

まず、クエリ系の基本方針として、「あるクエリについて解くにはどうするか」というのがある。
ここから考えよう。
　
ある文字列Sについて、文字列A,B,Cを独立した部分文字列として持つか判定しよう。
これはDPでできる。
dp[a][b][c] := 文字列Sの最小で何文字目で、文字列Aがa番目まで、文字列Bがb番目まで、文字列Cがc番目まで含めることができるか
dp[a][b][c]からの遷移を考えると、dp[a+1][b][c]はdp[a][b][c]番目の文字より右にある最も近い文字A[a]の場所になる。
よって、各遷移は1通りなので、全部で3通りの遷移。
状態数はO(250^3)なので、全体では間に合う。
　
これをクエリ問題に変換する。
実は、このdp配列は、各クエリで差分だけ計算することによって高速に計算ができる。
前のクエリまでで、1番目の文字列キューの長さがNA[0], 2番目がNA[1], 3番目がNA[2]であるとする。
つまり、dp[ NA[0] ][ NA[1] ][ NA[2] ]までは構築されているとする。
i=1の場合しか説明しないが、他の場合も同様に頑張る。
　
「+ i c」
i=1の時を考える。
すると、追加でdp[ NA[0]+1 ][ b ][ c ]を構築する必要が出てくる。
追加で構築する必要のある箇所はb,cの部分でO(250^2)である。
しかも、ここが増えたことで、もともと構築済みの部分に変更は無い。
よって、O(250^2)で差分計算が可能。
　
「- i」
i=1の時を考える。
すると、dp[ NA[0]+1 ][ b ][ c ]をリセットする必要が出てくる。
リセットする必要のある箇所はb,cの部分でO(250^2)である。
しかも、ここが増えたことで、残りの部分に変更は無い。
よって、O(250^2)で差分計算が可能。
　
これで全体O(1000*250^2)なので間に合う。

int N, Q; string S;
string A[3]; int NA[3];
int dp[251][251][251];
StringMaster sm;
//---------------------------------------------------------------------------------------------------
int f(int a, int b, int c, int i) {
	if (0 <= dp[a][b][c]) return dp[a][b][c];
	dp[a][b][c] = inf;

	// dp[a][b][c]
	if (0 < a) {
		if (f(a - 1, b, c, i) < inf) {
			chmin(dp[a][b][c], sm.gomigi(f(a - 1, b, c, i), A[0][a - 1] - 'a'));
		}
	}
	if (0 < b) {
		if (f(a, b - 1, c, i) < inf) {
			chmin(dp[a][b][c], sm.gomigi(f(a, b - 1, c, i), A[1][b - 1] - 'a'));
		}
	}
	if (0 < c) {
		if (f(a, b, c - 1, i) < inf) {
			chmin(dp[a][b][c], sm.gomigi(f(a, b, c - 1, i), A[2][c - 1] - 'a'));
		}
	}

	return dp[a][b][c];
}
//---------------------------------------------------------------------------------------------------
void add(int i, char c) {
	A[i] += c; NA[i]++;

	if (i == 0) {
		rep(b, 0, NA[1] + 1) rep(c, 0, NA[2] + 1) dp[NA[0]][b][c] = -1;
	}

	if (i == 1) {
		rep(a, 0, NA[0] + 1) rep(c, 0, NA[2] + 1) dp[a][NA[1]][c] = -1;
	}

	if (i == 2) {
		rep(a, 0, NA[0] + 1) rep(b, 0, NA[1] + 1) dp[a][b][NA[2]] = -1;
	}

	f(NA[0], NA[1], NA[2], i);
}
//---------------------------------------------------------------------------------------------------
void back(int i) {

	if (i == 0) {
		rep(b, 0, NA[1] + 1) rep(c, 0, NA[2] + 1) {
			dp[NA[0]][b][c] = inf;
		}
	}

	if (i == 1) {
		rep(a, 0, NA[0] + 1) rep(c, 0, NA[2] + 1) {
			dp[a][NA[1]][c] = inf;
		}
	}

	if (i == 2) {
		rep(a, 0, NA[0] + 1) rep(b, 0, NA[1] + 1) {
			dp[a][b][NA[2]] = inf;
		}
	}

	NA[i]--;
	A[i].pop_back();

	if (NA[0] + NA[1] + NA[2] == 0) dp[0][0][0] = 0;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> Q >> S;
	S = "a" + S;
	fore(c, S) c -= 'a';
	sm.init(S);
	sm.initgo();

	rep(a, 0, 251) rep(b, 0, 251) rep(c, 0, 251) dp[a][b][c] = inf;
	dp[0][0][0] = 0;

	rep(q, 0, Q) {
		char t; cin >> t;
		if (t == '+') {
			int i; char c; cin >> i >> c; i--;
			add(i, c);
		}
		else {
			int i; cin >> i; i--;
			back(i);
		}

		if (dp[NA[0]][NA[1]][NA[2]] < inf) printf("YES\n");
		else printf("NO\n");
	}
}