Codeforces ECR #131 : E. Text Editor

Eでもだいぶ苦戦してたな…。
https://codeforces.com/contest/1701/problem/E

問題

文字列S,Tが与えられる。
文字列Sが書かれたテキストボックスに対し、以下のキー操作を任意の順で行えるとする。

• 左
• 右
• Home
• End
• Backspace

SをTにするのに最小何回キー操作が必要か。

解法

右キーとBackspaceキーでSの前半何文字かをTの前半何文字かに一致させた後、Endキーを押して左キーとBackspaceキーで、SのsuffixをTのsuffixに一致させていけばよい。
これには以下の値をDPで求めて行くとよい。

Prefix(i,j) := カーソルが先頭にある状態で、Sの先頭i文字をTの先頭j文字に一致させる最小キー操作回数
Suffix(i,j) := カーソルが末尾にある状態で、Sのi文字目以降をTのj文字目以降に一致させる最小キー操作回数

int Q,N,M;
string S,T;

int pref[5050][5050];
int suf[5050][5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>N>>M>>S>>T;
		
		FOR(i,N+1) FOR(j,N+1) pref[i][j]=suf[i][j]=1<<20;
		FOR(i,N+1) {
			FOR(j,min(i,M)+1) {
				if(i==0||j==0) pref[i][j]=2*i;
				else {
					if(S[i-1]==T[j-1]) {
						pref[i][j]=min(pref[i][j],pref[i-1][j-1]);
					}
					if(pref[i-1][j]<1<<20) {
						pref[i][j]=min(pref[i][j],i+(i-j));
					}
				}
			}
		}
		for(i=N;i>=0;i--) {
			for(j=M;j>=max(0,M-(N-i));j--) {
				if(j==M) suf[i][j]=N-i;
				else if(i<N) {
					if(S[i]==T[j]) {
						suf[i][j]=min(suf[i][j],suf[i+1][j+1]+1);
					}
					if(suf[i+1][j]<1<<20) {
						suf[i][j]=min(suf[i][j],N-i);
					}
				}
			}
		}
		
		int ret=1<<20;
		FOR(i,N+1) FOR(j,M+1) {
			if(i==j&&pref[i][j]==0) {
				ret=min(ret,suf[i][j]);
			}
			else {
				ret=min(ret,suf[i][j]+1+pref[i][j]);
			}
			//cout<<"!"<<i<<j<<" "<<pref[i][j]<<" "<<suf[i][j]<<" "<<ret<<endl;
		}
		if(ret>1<<19) ret=-1;
		cout<<ret<<endl;
	}
}

まとめ

なんで本番こんな手間取ってるんだろ。