TopCoder SRM434 Div1Hard

問題

コンマ区切りのリストで、leading-zeroを持たない正整数の単調増加列であるリストを、increasing-listと呼ぶ。数字、コンマ、?からなる文字列maskが与えられる。maskの"?"を適切に置き換えて、increasing-listを作れ。複数あるなら、辞書順最小のものを返せ。

解法

「dp[i][j] := maskの[0, i)の範囲で、各数の桁数がj桁以下である場合の最善の答え」としてDP。

コード

#include <string>
#include <vector>

using namespace std;

class IncreasingLists
{
	string dp[51][51], in;
	int N;
	
	string make_seq(vector<string> v)
	{
		vector<string> _v = v;
		string bas = "00000000000000000000000000000000000000000000000000";
		for(int i=0;i<v.size();i++){
			for(int j=0;j<v[i].size();j++) if(v[i][j]=='?') v[i][j] = '9';
			if(v[i] <= bas) return string("q");
			for(int j=0;j<v[i].size();j++) if(_v[i][j]=='?'){
				while(v[i] > bas && ((j==0&&v[i][j]>='1') || (j>0&&v[i][j]>='0')) ) v[i][j]--;
				v[i][j]++;
			}
			bas = v[i];
			if(bas[0]=='0') return string("q");
		}
		string ret;
		for(int i=0;i<v.size();i++){
			if(i==0) ret += v[i];
			else ret += string(",") + v[i];
		}
		return ret;
	}
	
	string validate(string s)
	{
		for(int i=0;i<s.size();i++) if(s[i]=='q') return string("q");
		return s;
	}
	
public:
	string makeIncreasingList(string mask)
	{
		in = mask; N = in.size();
		
		for(int i=0;i<=N;i++){
			for(int j=0;j<=N;j++){
				dp[i][j] = string("q");
				if(i==0 || j==0){
					continue;
				}
				dp[i][j] = dp[i][j-1];
				for(int k=i-(j+1);;k-=j+1){
					for(int l=k+j;l>k;l--) if(mask[l]==',') goto nex;
					if(k<0){
						if(k<-1) break;
						vector<string> tmp;
						for(int l=0;l<i;l+=j+1) tmp.push_back(mask.substr(l, j));
						
						dp[i][j] = min(dp[i][j], make_seq(tmp));
					}else{
						if(mask[k]!='?'&&mask[k]!=',') break;
						vector<string> tmp;
						for(int l=k+1;l<i;l+=j+1) tmp.push_back(mask.substr(l, j));
						
						dp[i][j] = min(dp[i][j], validate(dp[k][j-1] + string(",") + make_seq(tmp)));
					}
					continue;
nex:
					break;
				}
			}
		}
		
		string ret = dp[N][N];
		for(int i=0;i<ret.size();i++) if(ret[i]=='q') return string("impossible");
		return ret;
	}
};