TopCoder SRM 727 Div1 Easy OnlySanta

なぜ年明けに出した…。
https://community.topcoder.com/stat?c=problem_statement&pm=14776

問題

文字列Sが与えられる。
この文字にいくつか文字を足し、部分列として"SANTA"を含むが、"SATAN"を含まないようにせよ。

解法

先のDiv2 Hardの類題である。
TopCoder SRM 727 Div2 Hard ManageSubsequences - kmjp's blog

A="SANTA", B="SATAN"とし、同様にDPしよう。
最小値を求める代わりに、DPを復元して文字列を生成すればよい。

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;
	}
}

まとめ

結果的に出なくて助かったのか…。