AtCoder ARC #131 : F - ARC Stamp

あとちょっとだった。
https://atcoder.jp/contests/arc131/tasks/arc131_f

問題

N文字の文字列Sがあったとする。SはA,R,Cの3種類の文字で構築される。
ここで、連続する3文字を選び、"ARC"で置き換える処理を最大K回行ったところ、Tとなった。

T,Kが与えられたとき、あり得るSを答えよ。

解法

Tにおいて、以下の構成は置き換え処理によって生成された可能性がある。

• "ARC": "ARC"以外の状態から、置き換えを行った。
• "A**"・"AR*": "A","AR"以外の状態から置き換えを行った後、1文字・2文字右隣において置き換えが生じた。
• "**C"・"*RC": "C","RC"以外の状態から置き換えを行った後、2文字・1文字左隣において置き換えが生じた。
• "*R*": "R"以外の状態から置き換えを行った後、両隣で置き換えが生じた。

ここから「ここを置き換えるなら、後で左右でもこのような置き換えがなければいけない」という条件が生じる。
この条件は左右両方向に生じて面倒だが、先読みを行うことで左側から順に数えることができる。

dp(n,k,b) := Tの先頭n文字まで見たとき、すでに置き換えがk回行われている状態で、さらに右の位置に置き換えが必要or不必要がbで与えられるとき、そのような置き換え方の組み合わせ
として順次計算していこう。

注意点として、置き換え前と置き換え後で同じ文字列なら、置き換え回数を消費しなくて良い点に気をつけること。

string T;
int N,K;
const ll mo=998244353;


ll from[5050][2];
ll to[5050][2];
int status[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T>>K;
	N=T.size();
	K=min(K,N);
	
	FOR(i,N+1) status[i]=-5;
	
	FOR(x,N) {
		FOR(i,N) {
			if(i+3<=N) {
				string C=T.substr(i,3);
				if(C=="ARC") status[i]=0,status[i+1]=status[i+2]=-4;
				if(C=="AR*") status[i]=2,status[i+1]=-4;
				if(C=="A**") status[i]=1;
				if(C=="**C") status[i+2]=-1;
				if(C=="*RC") status[i+1]=-2,status[i+2]=-4;
				if(C=="*R*") status[i+1]=3;
			}
			if(status[i]>=-4) T[i]='*';
		}
	}
	
	from[0][0]=1;
	int pre=-5;
	FOR(i,N) {
		if(status[i]==-4) continue;
		ZERO(to);
		FOR(j,i+2) {
			// not cover
			(to[j][0]+=from[j][0])%=mo;
			if(status[i]==-5) continue;
			
			// cover
			if(status[i]==0) {
				(to[j+1][1]+=27*from[j][0])%=mo;
				(to[j+1][0]+=26*from[j][0])%=mo;
				if(pre==3||pre==1||pre==2) {
					(to[j+1][1]+=27*from[j][1])%=mo;
					(to[j+1][0]+=27*from[j][1])%=mo;
				}
			}
			else if(status[i]==3) {
				(to[j+1][1]+=2*from[j][1])%=mo;
			}
			else if(status[i]>0) {
				int mul=(status[i]==1)?3:9;
				(to[j+1][1]+=(mul-1)*from[j][0])%=mo;
				if(pre==3||pre==1||pre==2) {
					(to[j+1][1]+=mul*from[j][1])%=mo;
				}
				
			}
			else {
				int mul=(status[i]==-1)?3:9;
				(to[j+1][0]+=(mul-1)*from[j][1])%=mo;
				(to[j+1][1]+=mul*from[j][1])%=mo;
			}
		}
		swap(from,to);
		pre=status[i];
	}
	
	ll ret=0;
	for(i=0;i<=K;i++) ret+=from[i][0];
	cout<<ret%mo<<endl;
	
	
}

まとめ

最近のARCのFの中では簡単な方な気がする。