Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-12-30

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

| 12:00 | 過去問マラソン(#6続き):SRM149 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#6続き):SRM149 - naoya_t@topcoder 過去問マラソン(#6続き):SRM149 - naoya_t@topcoder のブックマークコメント

Medium(500): MessageMess

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

  • 1投目(21'15'') ... failed system test
    • IMPOSSIBLEな時に全部なめててTLE
    • メモ化ちゃんとしないと
  • 2投目 ... failed
    • まだぜんぜん遅い
    • 同じところまで2度来たら、1度目の結果次第で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!";
    }
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091230