cafelier@SRM

SRM488 500

あとで | 17:36 |

• 本番中submitした500は
  • stringの実装によっては RE
    • str[str.size()]=='\0' を返してくる実装なら生き延びてしまう
  • それでもたぶんデータセットによっては WA
    • 意図せず s.substr(i, 巨大) になって意図せず s.substr(i, s.size()-i) にクリップされるので、それでまともに動く気が…
  • そもそも O(N^4) のつもりだったけど実は O(N^5) の最悪時間計算量なので TLE
• という「何が出るかな？」状態だったはずなのに Accept されてしまいました…

• 書き直し
• 顧客が本番中に本当に書きたかったもの：

class TheBoringStoreDivOne { public:
   // entry point
   string J, B;
   string find(string J, string B) 
   {
      this->J=J; this->B=B; return solve();
   }

   // just for clarifying types
   typedef int           J_index, B_index;
   typedef pair<int,int> J_sub,   B_sub;
   string jsub(J_index js, J_index je) { return J.substr(js, je-js); }
   string bsub(B_index bs, B_index be) { return B.substr(bs, be-bs); }

   // update if better
   void update(string* a, const string& b)
   {
      if( a->size()<b.size() || (a->size()==b.size() && *a>b) )
         *a = b;
   }

   // O(|J|^4) in total
   string solve()
   {
      string result;
      for(J_index js=0;    js< J.size(); ++js)
      for(J_index je=js+1; je<=J.size(); ++je) // for each J[js, je)
      for(J_index ks=0;    ks< J.size(); ++ks) // try each J[ks, ks+k) which ...
      {
         // ... is a maximal nonempty prefix of J[js, je) not intersecting with it
         int k;
         for(k=0; js+k<je && ks+k<J.size() && (ks+k<js || je<=ks); ++k)
            if( J[js+k] != J[ks+k] )
               break;
         if( k==0 )
            continue;

         // we have J[js, js+k)+J[js+k, je) in J, so we want              m in B
         //         J[ks, ks+k)                              J[js+k,je) + m
         string m = findInB(J_sub(js+k,je));
         if( !m.empty() )
            update(&result, jsub(js,je)+m);
      }
      return result;
   }

   // O(|J|^2 |B|^2) in total
   map<J_sub, string> memo_fib;
   string findInB(J_sub key)
   {
      if( memo_fib.count(key) )
         return memo_fib[key];

      string result;
      for(string::iterator it=B.begin(); it!=B.end(); ++it) // for each B[ks,ke)==key
      {
         it = search(it, B.end(), J.begin()+key.first, J.begin()+key.second);
         if( it == B.end() )
            break;
         B_index ks = it - B.begin();
         B_index ke = ks + (key.second - key.first);

         // try all B[ks, ke)+B[ke, kee), and try to find another B[ke, kee) before ks or after kee
         for(B_index kee=ke+1; kee<=B.size(); ++kee)
            if( canFindBefore(ks, B_sub(ke,kee)) || canFindAfter(kee, B_sub(ke,kee)) )
               update(&result, bsub(ke,kee));
      }
      return memo_fib[key] = result;
   }

   // O(|B|^4) in total : for each substring m of B, the first and last occurence is memoized
   bool canFindBefore(B_index bi, B_sub m) { return firstOccurence(m)+(m.second-m.first) <= bi; }
   bool canFindAfter (B_index bi, B_sub m) { return bi <= lastOccurence(m)-(m.second-m.first); }

   map<B_sub, B_index> memo_fo;
   B_index firstOccurence(B_sub m)
   {
      if( memo_fo.count(m) )
         return memo_fo[m];
      return memo_fo[m] = search(B.begin(), B.end(), B.begin()+m.first, B.begin()+m.second)-B.begin();
   }

   map<B_sub, B_index> memo_lo;
   B_index lastOccurence(B_sub m)
   {
      if( memo_lo.count(m) )
         return memo_lo[m];
      int mrs = B.size() - m.second;
      int mre = B.size() - m.first;
      return memo_lo[m] = B.size() - (search(B.rbegin(), B.rend(), B.rbegin()+mrs, B.rbegin()+mre)-B.rbegin());
   }
};

• にしても実装結構ヘビーですし
• 想定解法はもっと綺麗なのがあるんだと思いますが。