naoya_t@topcoder

SRM432 Div1 Medium: GroupedWord

過去問, 練習 | 21:21 |

昨日のSRMの500点問題を解いてみる。

#define sz(a)  int((a).size())
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define lastc(str) (*((str).end()-1))

typedef long long ll;
typedef vector<int> vi;

class GroupedWord {
  int n;
  vs ps;
  vi chs;

  pair<int,string> sub(const string &str, int len, ll av, ll chs_used){
    if(len==n) return make_pair(1,str);
    if(av==0LL) return make_pair(0,"");
    pair<int,string> p=make_pair(0,"");
    int last = sz(str)>0 ? lastc(str) : -1;
    for(ll i=0,mi=1LL;i<n;i++,mi<<=1){
      if(!(av&mi)) continue;
      ll dub=chs[i]&chs_used;
      if(ps[i][0]==last) dub-=(1LL<<(last-'a'));
      if(dub) continue;
      int ilast = lastc(ps[i]);
      ll av_new=av-mi, chs_new=chs_used|chs[i];
      for(ll j=0,mj=1LL;j<n;j++,mj<<=1){
        //if(j==i)continue;
        if((av_new&mj)==0) continue;
        if((chs_new&chs[j])==0) continue;
        if(ilast==ps[j][0]) continue;
        av_new-=mj;
      }
      pair<int,string> s=sub(str+ps[i],len+1,av_new,chs_new);
      if(p.first + s.first >= 2) {
        if(p.second!=s.second) return make_pair(2,"MANY");
      }
      if(s.first>0) p=s;
    }
    return p;
  }
  ll used_chars(const string &s){
    ll m=0LL;
    rep(i,sz(s)){
      ll mi=1LL<<(s[i]-'a');
      if((m&mi) && (i>0 && s[i-1]!=s[i])) return -1;
      m |= mi;
    }
    return m;
  }
 public:
  string restore(vector<string> parts) {
    n=sz(parts);
    ps=parts;
    chs.resize(n);
    rep(i,n) if((chs[i]=used_chars(parts[i]))<0) return "IMPOSSIBLE";
    pair<int,string> result = sub("", 0, (1LL<<n)-1LL, 0LL);
    switch(result.first){
      case 0: return "IMPOSSIBLE";
      case 1: return result.second;
      default: return "MANY";
    }
  }
};

TLE。

メモ化バージョンを作ってみたがローカルで28秒（おそらくサーバだと8〜10秒程度）かかるケース(#27)がある。

INPUT: {{"fffff", "hggggggg", "fh", "hhh", "ddde", "ddddd", "cccccc", "ccccoo", "oooodd", "cccccc", "ooooooo", "oo", "eeeeeeeee", "ee", "ddddddd", "ggggggg", "fff"}}
EXPECTED: "MANY"

後でまた考えよう。