Codeforces 162D (264D) Colorful Stones

問題

R, G, Bの色の石が2列に並んでいる。
ひとつ目の列は文字列sで表され、もうひとつの列はtで表される。

リスがsの最初の石に乗っていて、ネコがtの最初の石に乗っている。
この状態から、以下の動作を好きなだけ繰り返すことができる。

R, G, Bのどれかの色を選ぶ。
その色の石に乗っている動物は、次の石に進む。
ただし、次の石がない場合、その色を選ぶことはできなない。

リスとネコの位置を(x, y)と表すことにすると、
(x, y)は何通りの異なる値を取ることができるか、求めよ。

制約条件

sの文字数≦10^6
tの文字数≦10^6

方針

リスがi番目の石にいるときのネコの位置の範囲を絞り込む。
ネコのいられる最も小さい番号をl[i], 最も大きい番号をr[i]とする。

l[i], r[i]はl[i - 1], r[i - 1]から簡単に計算できる。
l[i]は単にl[i - 1]から1つだけ進めればよくて、
r[i]は、r[i - 1]から1つ進めたあと、リスが動かない範囲でできるだけ進めればよい。

このl[i]からr[i]の中で、ネコが存在できない石が存在することがある。
それは、

....RG...
..........GR....

のように、色が互い違いになっているような場所。
（上でいうと右上のGにリスが、右下のRにネコが同時にいることはできない）

なので、このような場合を引く。
これは累積和を使えば、一回あたりO(1)でできる。

ソースコード

const int MX = 1000010;
int n, m;
int a[MX], b[MX], pos[MX][3];
int l[MX], r[MX];
int s1[MX][9], s2[MX][9];
string s, t;

void in(string &s, int &n, int *a, int sum[MX][9]){
	cin >> s;
	n = s.size();
	rep(i, n){
		if(s[i] == 'R') a[i] = 0;
		else if(s[i] == 'G') a[i] = 1;
		else a[i] = 2;
	}
	for(int i = 1; i < n; i++){
		rep(j, 9) sum[i][j] = sum[i - 1][j];
		sum[i][a[i] * 3 + a[i - 1]]++;
	}
}
int main(){
	in(s, n, a, s1);
	in(t, m, b, s2);
	
	rep(j, 3) pos[m][j] = m;
	for(int i = m - 1; i >= 0; i--) rep(j, 3){
		pos[i][j] = b[i] == j ? i : pos[i + 1][j];
	}
	
	l[0] = 0;
	r[0] = min(m - 1, pos[0][a[0]]);
	ll ans = r[0] - l[0] + 1;
	
	for(int i = 1; i < n; i++){
		l[i] = (b[l[i - 1]] == a[i - 1] ? 1 : 0) + l[i - 1];
		r[i] = pos[(b[r[i - 1]] == a[i - 1] ? 1 : 0) + r[i - 1]][a[i]];
		r[i] = min(m - 1, r[i]);
		
		if(l[i] >= m) break;
		
		ans += r[i] - l[i] + 1;
		int c = a[i] + a[i - 1] * 3;
		if(a[i] != a[i - 1]) ans -= s2[r[i]][c] - s2[max(0, l[i] - 1)][c];
	}
	cout << ans << endl;
	
	return 0;
}