TopCoder SRM 727 Div2 Hard ManageSubsequences

EasyもMediumも1発ACしなかったので、出なくて助かったかも。
https://community.topcoder.com/stat?c=problem_statement&pm=14794

問題

文字列S,A,Bが与えられる。
Sにいくつか文字を追加し、Aを部分列として含みつつBを含まないようにしたい。
最小何文字追加すればよいか。

解法

以下の状態を考える。
f(s,a,b) := Sのprefix s文字を含む文字列のうち、Aのprefix a文字を含み、Bのprefix b文字を含むものを生成する際、Sのprefix s文字に必要な追加文字数の最小値

f(|S|,|A|,b)のうちb＜|B|であるものの最小値が求める解となる。
f(s,a,b)の状態の文字に対し、S[s]もしくはA[a]相当の文字を追加することを考え、状態遷移後の状態を求めていけばよい。
f(s,a,b)にS[s]相当の文字を追加する場合、f(s+1,a+(S[s]==A[a]),b+(S[s]==B[b])) = f(s,a,b)となりうるし、f(s,a,b)にA[a]相当の文字を追加する場合、f(s+ (S[s]==A[a]),a+1,b+(A[a]==B[b])) = f(s,a,b)+1となりうる。

int dp[303][303][303];

class ManageSubsequences {
	public:
	
	int minAdded(string S, string A, string B) {
		int LS=S.size();
		int LA=A.size();
		int LB=B.size();
		int s,a,b;
		FOR(s,LS+1) FOR(a,LA+1) FOR(b,LB+1) dp[s][a][b]=1010;
		dp[0][0][0]=0;
		
		int mi=1010;
		
		FOR(s,LS+1) FOR(a,LA+1) FOR(b,LB) if(dp[s][a][b]<1010) {
			if(a==LA && s==LS) {
				mi=min(mi,dp[s][a][b]);
				continue;
			}
			
			// take s
			if(s<LS) {
				int aa=a+(a<LA && S[s]==A[a]);
				int bb=b+(S[s]==B[b]);
				dp[s+1][aa][bb]=min(dp[s+1][aa][bb],dp[s][a][b]);
			}
			// take a
			if(a<LA) {
				int ss=s+(s<LS && S[s]==A[a]);
				int bb=b+(A[a]==B[b]);
				dp[ss][a+1][bb]=min(dp[ss][a+1][bb],dp[s][a][b]+1);
			}
		}
			
		
		if(mi==1010) mi=-1;
		return mi;
	}
}

まとめ

これは900ptでもいいかも。