SRM414 div1 medium
貪欲でOK。
#include <string> #include <vector> using namespace std; class StringInterspersal { public: string minimum(vector <string> W) { string ans; int n=W.size(); int s=0; for(int i=0;i<n;i++) s+=W[i].size(); vector<int> used(n,0); while(ans.size()<s) { char c='Z'+1; int p; for(int i=0;i<n;i++) if(used[i]<W[i].size()) { if(W[i][used[i]]<c) c=W[i][used[i]],p=i; else if(W[i][used[i]]==c) { int j; for(j=0;j<min(W[p].size()-used[p],W[i].size()-used[i]);j++) if(W[p][j+used[p]]!=W[i][j+used[i]]) break; if(j+used[p]==W[p].size()) p=i; else if(j+used[i]==W[i].size()) ; else if(W[p][j+used[p]]<W[i][j+used[i]]) ; else p=i; } } ans+=c; used[p]++; } return ans; } };