Codeforces ECR #082 : E. Erase Subsequences

2/12開催…。
https://codeforces.com/contest/1303/problem/E

問題

文字列S,Tが与えられる。
初期状態で空の文字列Pに対し、以下を最大2回繰り返す。

• Sの部分列を定める。
• Sからそれらを取り除いて隙間を詰め、また取り除いたものをPの末尾に追加する

P=Tとすることが可能か答えよ。

解法

1周目で何文字取るか、を総当たりして、その中で各文字を1周目・2周目・不採用のどれにするか愚直に総当たりすればよい。

int A;
string S,T;
int X,Y;

int dp[404][404];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A;
	while(A--) {
		cin>>S>>T;
		X=S.size();
		Y=T.size();
		MINUS(dp);
		for(i=1;i<=Y;i++) dp[0][i]=i;
		FORR(c,S) {
			for(x=X;x>=0;x--) for(y=X;y>=0;y--) if(dp[x][y]!=-1) {
				if(x!=y && x!=X && c==T[x]) dp[x+1][y]=max(dp[x+1][y],dp[x][y]);
				if(dp[x][y]!=X && c==T[dp[x][y]]) dp[x][y]++;
			}
		}
		int ok=0;
		FOR(i,Y+1) if(dp[i][i]==Y) ok=1;
		if(ok) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		
		
	}
}

まとめ

難易度の割に本番解かれていない印象。