SRM 516 Div2 Hard NetworkXMessageRecovery

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11239&rd=14541
文字列message[i]を部分列として持つような最短の文字列を返せ。複数ある場合は辞書式最小のものを返せ。なお各message[i]の文字はすべて異なる。

やりかた

Editorialを参考にしました。

このやりかたはmessage[i]の文字はすべて異なるという制約から、
単純に各文字列の先頭を見て今使えるかどうかを判定しながら、使える文字の内最小のものをそのターンで使用して、その文字列は先頭を取り除く、という感じにする。使用出来るか否かの判定については、各々の文字列の先頭を見て、その先頭の文字が、書く文字列の先頭以外の場所に現れるかどうかである。出現するときは使用できない。それより先に出現するべき文字があるからである。

つまり"abc", "bcf", "dea" とあったらまず最初の文字列の先頭'a'を見るが、これは最後の文字列"dea"の先頭より後ろに現れているので使用できない。次に２番めの文字列の先頭'b'を見る。しかしこれも最初の文字列"abc"の先頭より後ろに現れているので使用できない。次に３番目の文字列"dea"を見る。この先頭の'd'はどの文字列の先頭より後ろに現れていないので使用出来る。なのでこの'd'を使用し、"dea"は"ea"とする。
これを繰り返せば、'd'→'e'→'a'→'b'→'c'→'f'という文字列が得られてこれが答えになる。

以下ソース。

class NetworkXMessageRecovery {
public:
  string recover(vector <string> messages) {
    string result;
    int N = messages.size();
    while(1){
      const char inf = '{';
      char best = inf;
      for(int i = 0; i < N; i++){
	if(messages[i].size() == 0) continue;
	char good = messages[i][0];
	for(int j = 0; j < N; j++)
	  for(int k = 1; k < (int)messages[j].size(); k++)
	    if(good == messages[j][k]) good = inf;
	best = min(best, good);
      }
      if(best == inf) break;
      result += best;
      for(int i = 0; i < N; i++)
	if(messages[i].size() != 0 && messages[i][0] == best)
	  messages[i] = messages[i].substr(1);
    }
    return result;
  }
};

文字列中の文字はすべて異なるという制約を見落として見たため、全くおかしなことを繰り返していたし、そもそも絶対に間に合いっこない幅優先探索で全探査を試みていた。まったくだめだった。