TopCoderOpen 2018 Wildcard Round Hard CommonPalindromicSubsequences

普段のDiv1 Hardよりは簡単。まぁ間に合わなかったけど…。
http://community.topcoder.com/stat?c=problem_statement&pm=15010

問題

アルファベット小文字で構成される２つの文字列A,Bが与えられる。
空でない文字列Sのうち、以下を満たすのは何通りか。

• SはA,Bの部分文字列である。
• Sは回文である。

解法

まず手始めに、前処理としてA,Bの各位置において、左右最寄りの'a'～'z'の位置を求めておこう。
Sに'a'～'z'を含めていく場合、両端から貪欲にその文字を取っていくことを考えよう。

dp(AL,AR,BL,BR) := Sの前半何文字かはA[1..AL]およびB[1..BL]の部分文字列で、後半はA[AR...|A|]およびB[BR...|B|]の部分文字列で、それらは互いに回文を成すような組み合わせ

dp(0,|A|+1,0,|B|+1)=1から初めて、次にSに'a'～'z'を含む場合の位置を貪欲に求めていこう。
そして、dp(AL,AR,BL,BR)の値の2倍(Sを奇数長にする場合と偶数長にする場合の2通り)を解に加算する。ただしAL=ARまたはBL=BRのときはSは奇数長にしかできない。

int L[2][62][26];
int R[2][62][26];
ll dp[62][62][62][62];

class CommonPalindromicSubsequences {
	int N,M;
	public:
	long long count(string A, string B) {
		int i,j,x;
		int N=A.size();
		int M=B.size();
		FOR(i,26) {
			L[0][0][i]=L[1][0][i]=0;
			R[0][N+1][i]=N+1;
			R[1][M+1][i]=M+1;
		}
		for(i=1;i<=N+1;i++) {
			FOR(x,26) L[0][i][x]=L[0][i-1][x];
			if(i>=2) L[0][i][A[i-2]-'a']=i-1;
		}
		for(i=1;i<=M+1;i++) {
			FOR(x,26) L[1][i][x]=L[1][i-1][x];
			if(i>=2) L[1][i][B[i-2]-'a']=i-1;
		}
		for(i=N;i>=0;i--) {
			FOR(x,26) R[0][i][x]=R[0][i+1][x];
			if(i<N) R[0][i][A[i]-'a']=i+1;
		}
		for(i=M;i>=0;i--) {
			FOR(x,26) R[1][i][x]=R[1][i+1][x];
			if(i<M) R[1][i][B[i]-'a']=i+1;
		}
		
		ZERO(dp);
		ll ret=0;
		dp[0][N+1][0][M+1]=1;
		for(int alen=N+1;alen>=0;alen--) {
			for(int blen=M+1;blen>=0;blen--) {
				for(int AL=0;AL+alen<=N+1;AL++) {
					for(int BL=0;BL+blen<=M+1;BL++) {
						ll d=dp[AL][AL+alen][BL][BL+blen];
						if(d==0) continue;
						if(AL!=0) {
							ret+=d;
							if(alen&&blen) ret+=d;
						}
						FOR(i,26) {
							int nal=R[0][AL][i];
							int nar=L[0][AL+alen][i];
							int nbl=R[1][BL][i];
							int nbr=L[1][BL+blen][i];
							dp[nal][nar][nbl][nbr]+=d;
						}
					}
				}
			}
		}
		
		return ret;
	}
}

まとめ

Mediumでてこずるならこっち頑張っておけばよかった。