AtCoder ARC #110 (鹿島建設プログラミングコンテスト2020) : E - Shorten ABC

AGCで似たの出たのは覚えてたけど、それでもこれ系苦手。
https://atcoder.jp/contests/arc110/tasks/arc110_e

問題

ABCで構成された文字列Sがある。
Sに対し隣接した異なる2文字を選択し、その2文字をいずれでもない1文字に入れ替える、という処理を任意回数行うとする。
こうしてできる文字列は何通りか。

解法

A,B,Cを1,2,3に対応付けると、処理により得られる文字は、元の2文字のxorを取ったものである。
これは、最終的に1文字になる場合、どの順で処理しても同じ結果となることを示す。

f(k) := Sのk文字目以降で構成できる文字数
とし、f(k)をkの大きい順に求めてf(0)を答えよう。

もしkから何文字か貪欲に選び、A,B,Cのいずれを作れるか、はxorの累積和を取っておくと高速に求めることができる。
狙った文字を作れる最短の位置をtとする。その際、以下の3通りを考えよう。

• tが末尾の場合、f(k)に1を加算
• t以降1種類の文字しかない場合、2文字ずつ消すことが考えられる
• それ以外はどん欲にtを取り、すなわちf(k)+=f(t+1)とする。

int N;
string S;
int xo[1202020];
const ll mo=1000000007;
ll dp[1202020];
int num[1202020][4];
int ne[4];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,N) {
		S[i]=S[i]-'A'+1;
		num[i][S[i]]=1;
		xo[i+1]=xo[i]^S[i];
	}
	
	
	MINUS(ne);
	ne[xo[N]]=N;
	num[N][1]=num[N][2]=num[N][3]=1;
	for(i=N-1;i>=0;i--) {
		
		FOR(j,4) num[i][j]&=num[i+1][j];
		int add=0;
		// 全消し
		if((xo[N]^xo[i])>0&&((i==N-1)||(num[i][1]==0&&num[i][2]==0&&num[i][3]==0))) {
			add=1;
		}
		
		for(j=1;j<4;j++) {
			x=xo[i]^j;
			int t=ne[x];
			if(t==-1||t==N) continue;
			for(y=1;y<4;y++) if(num[t][y]) break;
			if(j==y&&t==i+1) {
				dp[i]+=1;
			}
			else if(y<4) {
				dp[i]+=1+(N-t)/2;
				if((N-t)%2==0) add=0;
			}
			else {
				dp[i]+=dp[t];
			}
			
			
		}
		dp[i]+=add;
		dp[i]%=mo;
		ne[xo[i]]=i;
	}
	cout<<dp[0]<<endl;
	
	
	
}

まとめ

A,B,Cを0,1,2に置いてしまったのが失敗。