TopCoderOpen 2013 Round2A Easy TheLargestString

TCO R2Aに参加。
Easyが300ptで嫌な予感。予想通りEasyを計算量溢れで落とした…。
まぁこの問題は正答率が低く、ランク減少はわずかにとどまったが。
http://community.topcoder.com/stat?c=problem_statement&pm=12494

問題

同じ長さの２つの文字列が与えられる。
両文字列からいくつか同じ位置の文字列を取り除いたうえで連結し、新たな文字列を作る。
このようにして作る文字列で辞書順最大のものを答える。

回答

本番は、再帰を使ってある位置の文字を使う・使わない場合の候補を列挙していた。
その後、これは計算量が危ないと思ってメモ化再帰にしたけど効果なく、結局計算時間溢れでアウト。

終了後、いくつか自分でDPを試してみたけどうまく行かず。
ほかの方の回答を参考にして自作。

文字列の後ろから順にDP。
文字列の各位置jについて、候補になりうるものをdp[j][l]に追加していく。
各位置jについて、j+1の候補に対してj番目の文字を使った場合により大きな文字列を作れるかを判定していく。
この処理はO(L^2)で終わるので計算量は余裕。

class TheLargestString {
	public:
	
	string find(string s, string t) {
		int i,j,l,L;
		pair<string,string> dp[60][60];
		string res;
		
		L=s.size();
		for(j=L-1;j>=0;j--) {
			FOR(l,59) {
				if(dp[j][l]<dp[j+1][l]) dp[j][l]=dp[j+1][l];
				
				if(l>0) {
					pair<string,string> ps=make_pair(s[j]+dp[j+1][l-1].first,t[j]+dp[j+1][l-1].second);
					if(dp[j][l]<ps) dp[j][l]=ps;
				}
				
				if(dp[j][l].first+dp[j][l].second>res) res = dp[j][l].first+dp[j][l].second;
			}
		}
		
		return res;
	}
};

まとめ

うーん、このDPはさらっと思いつかんわ…。
もっと精進が必要だ。
最近SRMが散々なのでR2Bはどうにかしたいところ。