TopCoder SRM 601 Div2 Hard WinterAndReindeers

Div2 HardはDiv1 Mediumに比べると、変わった発想よりも着実に実装しきるテクが求められているように感じるな。
http://community.topcoder.com/stat?c=problem_statement&pm=12872

問題

文字列A,B,Cが与えられる。以下の条件を満たす文字列Sの最大長を答えよ。

• SはAの部分文字列である。(Sの各要素はA中連続でなくてもよい)
• SはBの部分文字列である。(Sの各要素はB中連続でなくてもよい)
• CはSの部分文字列であり、Cの各要素はS中連続でなければならない。

解法

各文字列の最大長L=2500なので、処理をO(L^2)に押さえたい。
以下の３ステップで処理していく。いずれもO(L^2)。

1. SがA,Bの一部であり、CがSの一部であることから、CがA,Bの中で(不連続で良いので)存在しなければならない。
   1. A及びBの各位置を先頭としたとき、Cの文字列が全部登場し終える位置を計算する。この処理はA,Bの先頭位置がO(L)、その後Cの終える位置の検索にO(L)で計O(L^2)。
2. A,Bの最長部分文字列を求める。この際、DPを文字の先頭から行うものと末尾から行うものと２通り行う。一旦LCS計算をO(L^2)で行っておくと、A,Bの先頭何文字かにおけるLCSや、逆に末尾何文字かにおけるLCSをO(1)で求められるようになる。
3. A,Bの各位置について、そこをCの文字列が出てる先頭位置と仮定する。1の結果により、A,B中でCの要素がで終わる位置がわかる。後は2の結果より、A,Bの先頭位置より前の位置のLCSと、A,BでCの要素がで終わる位置以降のLCSがO(1)で求めることができる。

int maa[2600],mab[2600];
int dpb[2600][2600],dpe[2600][2600];

class WinterAndReindeers {
	public:
	string concatvec(vector <string> expr) { return accumulate(expr.begin(),expr.end(),string("")); }
	int getNumber(vector <string> allA, vector <string> allB, vector <string> allC) {
		int i,j,k,x,y,c,ma=0;
		string A=concatvec(allA);
		string B=concatvec(allB);
		string C=concatvec(allC);
		
		ZERO(maa);
		ZERO(mab);
		FOR(i,A.size()) {
			c=0;
			for(maa[i]=i;maa[i]<A.size();maa[i]++) {
				if(A[maa[i]]==C[c]) c++;
				if(c>=C.size()) break;
			}
		}
		FOR(i,B.size()) {
			c=0;
			for(mab[i]=i;mab[i]<B.size();mab[i]++) {
				if(B[mab[i]]==C[c]) c++;
				if(c>=C.size()) break;
			}
		}
		
		ZERO(dpb);ZERO(dpe);
		FOR(x,A.size()) FOR(y,B.size()) {
			if(A[x]==B[y]) dpb[x+1][y+1]=max(dpb[x+1][y+1],dpb[x][y]+1);
			dpb[x+1][y+1]=max(dpb[x+1][y+1],dpb[x][y+1]);
			dpb[x+1][y+1]=max(dpb[x+1][y+1],dpb[x+1][y]);
		}
		for(x=A.size();x>=1;x--) for(y=B.size();y>=1;y--) {
			if(A[x]==B[y]) dpe[x-1][y-1]=max(dpe[x-1][y-1],dpe[x][y]+1);
			dpe[x-1][y-1]=max(dpe[x-1][y-1],dpe[x][y-1]);
			dpe[x-1][y-1]=max(dpe[x-1][y-1],dpe[x-1][y]);
		}
		
		FOR(x,A.size()) FOR(y,B.size()) {
			if(maa[x]>=A.size() || mab[y]>=B.size()) continue;
			ma=max(ma,(int)C.size() + dpe[maa[x]][mab[y]] + dpb[x][y]-1);
		}
		
		return ma;
	}
};

まとめ

３文字間でLCS等を求める問題は最近Codeforcesでも見たな。
でもあれより簡単。