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; } };