naoya_t@topcoder

過去問マラソン(#6続き):SRM149

過去問マラソン | 12:00 |

Medium(500): MessageMess

最悪ケースがぱっと思いつかなくて処理量を過小評価しがちなので何とかしたい。

• 1投目(21'15'') ... failed system test
  • IMPOSSIBLEな時に全部なめててTLE
  • メモ化ちゃんとしないと
• 2投目 ... failed
  • まだぜんぜん遅い
  • 同じところまで２度来たら、１度目の結果次第でIMPOSSIBLE!かAMBIGUOUS!を返すように
• 3投目 ... passed

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)

typedef pair<int,string> status;

class MessageMess {
  vector<string> dict;
  int n;

  map<pair<string,string>,status> memo;
  map<string,int> visited;

  status sub(string msg,string curr){
    if (msg == "") return cons(1,curr);
    
    if (found(visited,msg)) return cons(visited[msg]>0?2:0,""); // 0 or 2

    pair<string,string> key = cons(msg,curr);
    if (found(memo,key)) return memo[key];

    int l=sz(msg);
    vector<string> res; int cnt;
    rep(i,n){
      string d = dict[i]; int dl=sz(d);
      if (dl > l) continue;
      if (d[0] != msg[0]) continue;
      if (d != msg.substr(0,dl)) continue;
      status subres = sub(msg.substr(dl), (curr == "") ? d : (curr + " " + d));
      switch(car(subres)) {
        case 0: break;
        case 1:
          if (cnt==1) {
            visited[msg]=2;
            return memo[key] = cons(2,"");
          } else {
            res.pb( cdr(subres) ); cnt++; break;
          }
        default:
          visited[msg] = 2;
          return memo[key] = cons(2,"");
      }
    }
    switch(sz(res)){
      case 0: visited[msg]=0; return memo[key] = cons(0,"");
      case 1: visited[msg]=1; return memo[key] = cons(1,res[0]);
      default: visited[msg]=2; return memo[key] = cons(2,"");
    }
  }
  
 public:
  string restore(vector<string> dictionary, string message) {
    dict = dictionary; 
    n=sz(dict);

    memo.clear(); visited.clear();

    status res = sub(message,"");
    switch(car(res)){
      case 0: return "IMPOSSIBLE!";
      case 1: return cdr(res);
      default: return "AMBIGUOUS!";
    }
  }
};