Codeforces #646 Div2 F. Rotating Substrings

これは割とシンプルな問題？
https://codeforces.com/contest/1363/problem/F

問題

2つの同じ長さの文字列S,Tが与えられる。
Sの部分文字列を選択し、1文字右にrotateすることを繰り返し、SをTにしたい。
必要な最小操作回数を答えよ。

解法

Sを右にrotateする代わりに、Tを左にrotateするものとする。

Sを構成する各文字の数とTと構成する各文字の数が一致しているのが前提。
基本的にはLCSと同じアプローチをとる。
f(x,y) := Sの先頭x文字とTの先頭y文字中(rotateで右に押し出した分は除く)x文字が一致している状態に至る最小処理回数

• S[x]==T[y]ならf(x+1,y+1) := f(x,y)
• y文字目を右に押し付けるf(x,y+1) := f(x,y)+1
• もし押し出した分にS[x]に一致する文字があれば、それを取り出してf(x+1,y) := f(x,y)

最後の「押し出した分にS[x]に一致する文字があれば」は、SとTの先頭何文字に、a～zが何文字ずつあるかを事前に求めておけばO(1)で判定できる。

int Q;
int N;
string S,T;

int dpdp[2020][2020];
int C[26][2020];
int D[26][2020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>N>>S>>T;
		ZERO(C);
		ZERO(D);
		FOR(i,N) {
			FOR(j,26) C[j][i+1]=C[j][i], D[j][i+1]=D[j][i];
			S[i]-='a';
			T[i]-='a';
			C[S[i]][i+1]++;
			D[T[i]][i+1]++;
		}
		
		FOR(x,N+1) FOR(y,N+1) dpdp[x][y]=101010;
		dpdp[0][0]=0;
		FOR(y,N+1) FOR(x,y+1) {
			if(y<N && S[x]==T[y]) dpdp[x+1][y+1]=min(dpdp[x+1][y+1],dpdp[x][y]);
			if(y<N) dpdp[x][y+1]=min(dpdp[x][y+1],dpdp[x][y]+1);
			if(D[S[x]][y]>C[S[x]][x]) dpdp[x+1][y]=min(dpdp[x+1][y],dpdp[x][y]);
		}
		
		int mi=dpdp[N][N];
		if(mi>2020) mi=-1;
		
		cout<<mi<<endl;
	}
}

まとめ

回答はシンプルだけど、本番さっと思いつくのはしんどそう。