naoya_t@topcoder

過去問マラソン(#13):SRM154

過去問マラソン | 23:23 |

Easy(350): CheatCode

• 配点350点て何
• 文字と必要打鍵数のペア、の配列をchainと仮に呼び
• 後だけでなく前に余計な文字を打つのもアリだとsample caseで気づき
• 途中に関係ない文字が入る場合はNG、ということにsample caseで気づき
• ていうか問題ちゃんと読んだほうが結果的に早いのでは?
• 149.37pt (50'25'') 時間かかりすぎ
• passed system test

#define sz(a)  int((a).size())
#define pb  push_back
#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())
#define cons(x,y) make_pair((x),(y))

typedef vector<pair<char,int> > chain;

class CheatCode {
  chain trans(string code) {
    chain co;
    int l=sz(code);
    char lastc=-1; int cn=0;
    rep(j,l){
      if (code[j]==lastc) cn++;
      else {
        if (lastc>0) co.pb(cons(lastc,cn));
        lastc=code[j]; cn=1;
      }
    }
    co.pb(cons(lastc,cn));
    return co;
  } 

  chain kp,code;

  bool accept(pair<char,int> c, pair<char,int> k) {
    if (c.first != k.first) return false;
    if (c.second > k.second) return false;
    return true;
  }
  bool match1(int ix,int kx) {
    if (ix == sz(code)) return true;
    if (sz(code)-ix > sz(kp)-kx) return false;
    if (!accept(code[ix],kp[kx])) return false;
 // for (int k=kx+1; k<=sz(kp); k++)
 //   if (match1(ix+1,k)) return true;
    if (match1(ix+1,kx+1)) return true;
    return false;
  }
  bool match() {
    int kpl = sz(kp), codel = sz(code);
    if (kpl<codel) return false;
    for(int kx=0; kx<=kpl-codel; kx++) {
      if (match1(0,kx)) return true;
    }
    return false;
  }
 public:
  vector<int> matches(string keyPresses, vector<string> codes) {
    kp = trans(keyPresses);
    vector<int> matched;
    rep(i,sz(codes)){
      code = trans(codes[i]);
      if (match()) matched.pb(i);
    }
    return matched;
  }
};

Medium(500)

Hard(1000)