SRM414: StringInterspersal

(問題概要)
文字列が幾つか与えられる。
すべての文字列が空になるまでどれかの文字列の先頭文字をくっつける操作を繰り返す。
辞書順最小の文字列を作りなさい。

(解法)
貪欲に最小なのをとっていく。
文字列がなくなるケースはあまり嬉しくないのを考慮。
最後にZをいっぱいつけておけば実装が簡単。
多分開いてから解くのに５分かかってない。

#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class StringInterspersal {
public:
  string minimum(vector <string> W);
};

string StringInterspersal::minimum(vector <string> W){
  const string suffix(51, 'Z');
  REP(i,W.size()) W[i] = W[i] + suffix;
  priority_queue<string, vector<string>, greater<string> > q(W.begin(), W.end());
  stringstream ss;
  while(q.size()){
    const string s = q.top(); q.pop();
    ss << s[0];
    if(s.size() > 1 + suffix.size()) q.push(s.substr(1));
  }
  return ss.str();
}