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

};