TopCoder SRM 556 Div1 Medium LeftRightDigitsGame2

Easyに続いてMediumに挑戦。
http://community.topcoder.com/stat?c=problem_statement&pm=12198

最大50文字分の0-9で構成される文字列Aと、同じ文字数からなる数値Bが与えられる。
文字列Aについて、先頭の文字を置いたあと、２文字目以降を既に置いた文字列の左右どちらかに置くという手続きを踏んだ場合、数値B以上で最小の数値を回答する。

回答ではDPで行っているものが多かったが、自分はメモ付再帰でやった。

文字列Aを上記手続きで変形し、文字列B以上の最小の数値を返す関数funcを再帰的に適用する。
この関数では、手続きの逆順、Aの末尾１文字に着目する。
Aの末尾を、それ以外の文字を変形した結果の先頭につけるか末尾につけるか、で文字列Bを超えられるか再帰的にチェックする。

Aの末尾を結果の先頭に持ってくる場合、

• Aの末尾がBの先頭より大きいなら、残りの文字列を最小化すればよい。
• Aの末尾がBの先頭と一致するなら、A・Bともに残りの文字をfuncに再帰的に適用
• Aの末尾がBの先頭より小さいならあきらめる

このとき、答えの先頭が0にならないよう注意する(ok0)

Aの末尾を結果の末尾に持ってくる場合、

• Aの末尾がBの末尾より大きいなら、A・Bともに残りの文字をfuncで再帰的に求める
• Aの末尾がBの末尾より小さいなら、Aの残りの文字列と、Bの残りの文字列を１足したものをfuncに再帰的に適用

文字列の最小化minstrでは、文字列中の最小の数値を探し、それを先頭に持ってくる場合で最小となるものを再帰的に求める。たとえば最小値がCとしてAAAAACBBBBBという文字列があったら、C + minstr(AAAAA) + BBBBBが最小値の候補になる。

class LeftRightDigitsGame2 {
	public:
	int N;
	string D;
	string L;
	string res;
	map<string,string> mp;
	map< pair<string, string>, string> mr;
	
	//1を足す
	string inc(string str) {
		int i,j;
		
		FOR(j,str.size()) {
			i = str.size()-1-j;
			if(str[i]=='9') str[i]='0';
			else {
				str[i]++;
				break;
			}
		}
		if(j==str.size()) return "";
		return str;
	}
	
	//最小文字列を探す
	string minstr(string str) {
		string res=string(str.size(),'a');
		string tres,l,r;
		int i,n,c;
		char mc='9';
		
		//最小
		n=str.size();
		if(n<=1) return str;
		FOR(i,n) if(str[i]<mc) mc=str[i];
		
		//同じ文字だけなら省略
		c=0;
		FOR(i,n) if(str[i]==mc) c++;
		if(c==n) return str;
		
		if(mp.find(str) != mp.end()) return mp[str];
		
		//mcが先頭にくる中で最小
		FOR(i,n) if(str[i]==mc) {
			l = minstr(str.substr(0,i));
			r = str.substr(i+1);
			tres = mc + l + r;
			if(tres<res) res = tres;
		}
		//_P("%s -> %s\n",str.c_str(),res.c_str());
		mp[str]=res;
		return res;
	}
	
	string func(string ld,string lb,bool ok0) {
		
		if(ld.size()==0) return "";
		if(ld.size()==1) {
			if(ok0==false && ld[0]=='0') return "a";
			if(ld[0]>=lb[0]) return ld;
			return "a";
		}
		
		string res = string(ld.size(),'a');
		string tres,lld,llb;
		
		//全部同じ？
		if(ld == string(ld.size(),ld[0])) {
			if(ld>=lb) return ld;
			return res;
		}
		pair<string, string> k = make_pair(ld,lb);
		if(ok0 && mr.find(k)!=mr.end()) return mr[k];
		
		//最後の文字で判定
		char c = ld[ld.size()-1];
		//左
		if(ok0 || c!='0') {
			lld = ld.substr(0,ld.size()-1);
			if(c==lb[0]) {
				//残り文字が満たすか？0もok
				llb = lb.substr(1);
				//_P("call left %s %s -> %s %s\n",ld.c_str(),lb.c_str(),lld.c_str(),llb.c_str());
				tres = c + func(lld,llb,true);
				if(tres.find('a',0) == string::npos && tres < res && tres>=lb) res=tres;
			}
			else if(c>lb[0]) {
				//残り文字で最小
				//_P("call min %s %s -> %s\n",ld.c_str(),lb.c_str(),lld.c_str());
				tres = c + minstr(lld);
				if(tres.find('a',0) == string::npos && tres < res && tres>=lb) res=tres;
			}
		}
		//右
		llb = lb.substr(0,lb.size()-1);
		lld = ld.substr(0,ld.size()-1);
		//繰り上がり
		if(c<lb[lb.size()-1]) llb=inc(llb);
		
		if(llb.size()>0) {
			//_P("call right %s %s -> %s %s\n",ld.c_str(),lb.c_str(),lld.c_str(),llb.c_str());
			tres = func(lld,llb,ok0) + c;
			if(tres.find('a',0) == string::npos && tres < res && tres>=lb) res=tres;
		}
		//_P("%s %s : %s\n",ld.c_str(),lb.c_str(),res.c_str());
		if(ok0) mr[k]=res;
		return res;
	}
	
	string minNumber(string digits, string lowerBound) {
		string res;
		D=digits;
		L=lowerBound;
		N=digits.size();
		mp.clear();
		mr.clear();
		
		res = func(D,L,false);
		
		//なかった場合
		if(res[0]=='a') res="";
		return res;
	}
}

まとめ

最初、メモ化無しでやったら概ね正しく動作したが、１ケース01だけで50桁あるケースでTLEした。
そのためメモ化を追加してクリア。
本番正答率も５割切ってるので、同じTLE食らったひとが多いと思われる。

今回は1TLEしたとはいえ、何とか解き切れて良かった。
今後もMedium安定クリアを目指したい。