Mujin Programming Challenge 2017 : C - Robot and String

Bでハマる前にこちらをやった方がよかったかも。
http://mujin-pc-2017.contest.atcoder.jp/tasks/mujin_pc_2017_c

問題

アルファベットで構成された文字列Tに対し、以下の処理を繰り返す。

• 同じ文字が連続する(T[i]=T[i+1])最小のiを求める。
  • 上記iが存在するなら、T[i]とT[i+1]を消し、代わりにアルファベットの次の文字に置き換える。
  • ただしT[i]=T[i+1]='z'ならこれらを消すだけで新しい文字は追加しない。

文字列Sに対し、Q個のクエリ(L,R)が与えられる。
部分文字列S[L...R]が上記処理を繰り返すと空文字になるか判定せよ。

解法

ダブリングで解く。
Sのindex iに対し、以下を考える。

• next[i][c] := 文字cに対し、S[i..(next[i][c]-1)]に処理を繰り返すとcが1文字だけ残るような最小のindex
• empty[i] := S[i..(empty[i][c]-1)]に処理を繰り返すと空文字になるような最小のindex

empty[i]を求められれば、empty[empty[L]]...とLに対しemptyを順に参照した際にRを含むかどうか判定することで、クエリに回答できる。
このempty[]を複数回たどる処理はempty[i]のダブリングを用いることでO(log|S|)で終えることができる。

残りはempty[i]を求めればよい。
こちらもダブリングの要領で行う。以下のようにnextとemptyを求めよう。

• next[i][S[i]] = i+1
• next[i][S[i]+1] = next[next[i][S[i]]][S[i]]
• next[i][S[i]+2] = next[next[i][S[i]+1]][S[i+1]]
• ...
• empty[i] = next[next[i][z]][z]
• next[i]['a'] = next[empty[i]]['a']
• next[i]['b'] = next[empty[i]]['b'] = next[next[i]['a']]['a'] (どちらも同じなのでどちらでもよい)
• next[i]['c'] = next[empty[i]]['c'] = next[next[i]['b']]['b']
• ...
• next[i][S[i]-1] = next[empty[i]][S[i]-1] = next[next[i][S[i]-2]][S[i]-2]

int N,Q;
string S;
int nex[505050][28];
int nexd[505050][20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	FORR(c,S) c-='a';
	N=S.size();
	FOR(i,27) nex[N][i]=nex[N+1][i]=N+1;
	FOR(i,20) nexd[N][i]=nexd[N+1][i]=N+1;
	for(i=N-1;i>=0;i--) {
		nex[i][S[i]]=i+1;
		for(j=S[i]+1;j<=26;j++) nex[i][j]=nex[nex[i][j-1]][j-1];
		for(j=0;j<S[i];j++) nex[i][j]=nex[nex[i][26]][j];
		nexd[i][0]=nex[i][26];
		for(j=0;j<19;j++) nexd[i][j+1]=nexd[nexd[i][j]][j];
	}
	cin>>Q;
	while(Q--) {
		int L,R;
		cin>>L>>R;
		L--;
		for(i=19;i>=0;i--) if(nexd[L][i]<=R) L=nexd[L][i];
		if(L==R) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	
}

まとめ

文字列系苦手だなぁ。