cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
SRM | |
SRM488 の成績・ソース (要ログイン) : AC/AC/- : また酷いコードを書いてしまった
あとで | |
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()); } };
presented by
cafelier/k.inaba
under
