TopCoder SRM 777 : Div1 Medium StringTransformation

しょうもないミスで落としたのもったいない。
https://community.topcoder.com/stat?c=problem_statement&pm=15775&rd=17802

問題

R,G,Bで構成されたN,M文字の文字列S、Tがある。
Sに対し以下の処理を繰り返し、Tにできるか判定せよ。

• 連続する4文字をp,q,r,sとしたとき、q==rかつp!=sならq,rを消すことができる。

解法

以下を考える。
f(L,R) := 元のS[L]とS[R]の間の文字を消し、S[L]とS[R]を隣接させることができるか
これは以下のいずれかを満たせば達成できる。

• LとRがもともと隣接
• S[L]!=S[R]で、f(L,x)かつf(x+1,R)かつS[x]==S[x+1]となるxが存在する

後者を愚直に行うとO(N^3)かかる。ここでbitsetを使い対応しよう。
g(L) := f(L,R)=1ならR bit目が1
h(R) := f(L,R)=1ならL bit目が1
neighbor := S[x]==S[x+1]ならx bit目が1

このとき、g(L) and (h(R)＞＞1) and neighbor が1bitでも立っていれば条件を満たす。
上記手順を[L,R]の区間の短い順に行い、f(L,R)およびg(L)を埋めたとする。

m(i) := S[0..i]がT[0..j]に対応づくならj bit目が0
とする。S[0]=T[0]であることを前提とし、m(0)を0 bit目だけ立っているものとする。
m(i+1) := m(i)でj bit目が立っているときのg(j)のor
を繰り返し、m(M)の(N-1) bit目が立っているか判定しよう。

int CD[2525][2525];
bitset<2600> L[2525],R[2525],nei,C[2525][3];

class StringTransformation {
	public:
	string getResult(string s, string t) {
		int N=s.size();
		int i,x,y;
		if(s[0]!=t[0] || s.back()!=t.back()) return "NO";
		FORR(c,s) {
			if(c=='R') c=0;
			if(c=='G') c=1;
			if(c=='B') c=2;
		}
		FORR(c,t) {
			if(c=='R') c=0;
			if(c=='G') c=1;
			if(c=='B') c=2;
		}
		
		FOR(x,N) L[x].reset(),R[x].reset();
		nei.reset();
		FOR(x,N-1) {
			L[x][x+1]=1;
			R[x+1][x]=1;
			if(s[x]==s[x+1]) nei[x]=1;
		}
		for(int len=4;len<=N;len+=2) {
			for(x=0;x+len<=N;x++) if(s[x]!=s[x+len-1]) {
				auto A=L[x]&(R[x+len-1]>>1)&nei;
				if(A.count()) {
					L[x][x+len-1]=1;
					R[x+len-1][x]=1;
				}
			}
		}
		FOR(x,N) {
			C[x][0].reset();
			C[x][1].reset();
			C[x][2].reset();
			FOR(y,N) if(L[x][y]) C[x][s[y]][y]=1;
		}
		bitset<2600> cur;
		cur[0]=1;
		for(i=1;i<t.size();i++) {
			bitset<2600> nex;
			FOR(x,N) {
				if(cur[x]) {
					nex |= C[x][t[i]];
					
				}
			}
			cur=nex;
		}
		if(cur[N-1]) return "YES";
		return "NO";
	}
}

まとめ

今回bitsetでゴリ押したけど、O(N^2)解法あるのかな？