d7959f8d5d 2014-07-22 kinaba: #include <iostream> d7959f8d5d 2014-07-22 kinaba: #include <sstream> d7959f8d5d 2014-07-22 kinaba: #include <iomanip> d7959f8d5d 2014-07-22 kinaba: #include <vector> d7959f8d5d 2014-07-22 kinaba: #include <string> d7959f8d5d 2014-07-22 kinaba: #include <map> d7959f8d5d 2014-07-22 kinaba: #include <set> d7959f8d5d 2014-07-22 kinaba: #include <algorithm> d7959f8d5d 2014-07-22 kinaba: #include <numeric> d7959f8d5d 2014-07-22 kinaba: #include <iterator> d7959f8d5d 2014-07-22 kinaba: #include <functional> d7959f8d5d 2014-07-22 kinaba: #include <complex> d7959f8d5d 2014-07-22 kinaba: #include <queue> d7959f8d5d 2014-07-22 kinaba: #include <stack> d7959f8d5d 2014-07-22 kinaba: #include <cmath> d7959f8d5d 2014-07-22 kinaba: #include <cassert> d7959f8d5d 2014-07-22 kinaba: #include <tuple> d7959f8d5d 2014-07-22 kinaba: using namespace std; d7959f8d5d 2014-07-22 kinaba: typedef long long LL; d7959f8d5d 2014-07-22 kinaba: typedef complex<double> CMP; d7959f8d5d 2014-07-22 kinaba: d7959f8d5d 2014-07-22 kinaba: class HappyLetterDiv1 { public: d7959f8d5d 2014-07-22 kinaba: string getHappyLetters(string letters) d7959f8d5d 2014-07-22 kinaba: { d7959f8d5d 2014-07-22 kinaba: set<char> cs(letters.begin(), letters.end()); d7959f8d5d 2014-07-22 kinaba: string ans; d7959f8d5d 2014-07-22 kinaba: for(char c: cs) d7959f8d5d 2014-07-22 kinaba: if(can_win(c, letters)) d7959f8d5d 2014-07-22 kinaba: ans += c; d7959f8d5d 2014-07-22 kinaba: return ans; d7959f8d5d 2014-07-22 kinaba: } d7959f8d5d 2014-07-22 kinaba: d7959f8d5d 2014-07-22 kinaba: bool can_win(char c, const string& s) d7959f8d5d 2014-07-22 kinaba: { d7959f8d5d 2014-07-22 kinaba: string rest; d7959f8d5d 2014-07-22 kinaba: string cs; d7959f8d5d 2014-07-22 kinaba: for(char ch: s) (ch==c ? cs : rest) += ch; d7959f8d5d 2014-07-22 kinaba: d7959f8d5d 2014-07-22 kinaba: if(rest.size()%2==1) { d7959f8d5d 2014-07-22 kinaba: rest += c; d7959f8d5d 2014-07-22 kinaba: cs.resize(cs.size()-1); d7959f8d5d 2014-07-22 kinaba: } d7959f8d5d 2014-07-22 kinaba: d7959f8d5d 2014-07-22 kinaba: while(!cs.empty()) { d7959f8d5d 2014-07-22 kinaba: if(can_erase(rest)) d7959f8d5d 2014-07-22 kinaba: return true; d7959f8d5d 2014-07-22 kinaba: if(cs.size()<2) d7959f8d5d 2014-07-22 kinaba: break; d7959f8d5d 2014-07-22 kinaba: rest += string(2, c); d7959f8d5d 2014-07-22 kinaba: cs.resize(cs.size()-2); d7959f8d5d 2014-07-22 kinaba: } d7959f8d5d 2014-07-22 kinaba: return false; d7959f8d5d 2014-07-22 kinaba: } d7959f8d5d 2014-07-22 kinaba: d7959f8d5d 2014-07-22 kinaba: bool can_erase(string s) d7959f8d5d 2014-07-22 kinaba: { d7959f8d5d 2014-07-22 kinaba: map<char, int> cnt; d7959f8d5d 2014-07-22 kinaba: int maxCnt = 0; d7959f8d5d 2014-07-22 kinaba: for(char c: s) maxCnt = max(maxCnt, ++cnt[c]); d7959f8d5d 2014-07-22 kinaba: return maxCnt*2 <= s.size(); d7959f8d5d 2014-07-22 kinaba: } d7959f8d5d 2014-07-22 kinaba: }; d7959f8d5d 2014-07-22 kinaba: d7959f8d5d 2014-07-22 kinaba: // BEGIN CUT HERE d7959f8d5d 2014-07-22 kinaba: #include <ctime> d7959f8d5d 2014-07-22 kinaba: double start_time; string timer() d7959f8d5d 2014-07-22 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } d7959f8d5d 2014-07-22 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) d7959f8d5d 2014-07-22 kinaba: { os << "{ "; d7959f8d5d 2014-07-22 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) d7959f8d5d 2014-07-22 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } d7959f8d5d 2014-07-22 kinaba: void verify_case(const string& Expected, const string& Received) { d7959f8d5d 2014-07-22 kinaba: bool ok = (Expected == Received); d7959f8d5d 2014-07-22 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; d7959f8d5d 2014-07-22 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } d7959f8d5d 2014-07-22 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); d7959f8d5d 2014-07-22 kinaba: #define END verify_case(_, HappyLetterDiv1().getHappyLetters(letters));} d7959f8d5d 2014-07-22 kinaba: int main(){ d7959f8d5d 2014-07-22 kinaba: d7959f8d5d 2014-07-22 kinaba: CASE(0) d7959f8d5d 2014-07-22 kinaba: string letters = "aabbacccc"; d7959f8d5d 2014-07-22 kinaba: string _ = "abc"; d7959f8d5d 2014-07-22 kinaba: END d7959f8d5d 2014-07-22 kinaba: CASE(1) d7959f8d5d 2014-07-22 kinaba: string letters = "aaaaaaaccdd"; d7959f8d5d 2014-07-22 kinaba: string _ = "a"; d7959f8d5d 2014-07-22 kinaba: END d7959f8d5d 2014-07-22 kinaba: CASE(2) d7959f8d5d 2014-07-22 kinaba: string letters = "ddabccadb"; d7959f8d5d 2014-07-22 kinaba: string _ = "abcd"; d7959f8d5d 2014-07-22 kinaba: END d7959f8d5d 2014-07-22 kinaba: CASE(3) d7959f8d5d 2014-07-22 kinaba: string letters = "aaabbb"; d7959f8d5d 2014-07-22 kinaba: string _ = ""; d7959f8d5d 2014-07-22 kinaba: END d7959f8d5d 2014-07-22 kinaba: CASE(4) d7959f8d5d 2014-07-22 kinaba: string letters = "rdokcogscosn"; d7959f8d5d 2014-07-22 kinaba: string _ = "cos"; d7959f8d5d 2014-07-22 kinaba: END d7959f8d5d 2014-07-22 kinaba: /* d7959f8d5d 2014-07-22 kinaba: CASE(5) d7959f8d5d 2014-07-22 kinaba: string letters = ; d7959f8d5d 2014-07-22 kinaba: string _ = ; d7959f8d5d 2014-07-22 kinaba: END d7959f8d5d 2014-07-22 kinaba: CASE(6) d7959f8d5d 2014-07-22 kinaba: string letters = ; d7959f8d5d 2014-07-22 kinaba: string _ = ; d7959f8d5d 2014-07-22 kinaba: END d7959f8d5d 2014-07-22 kinaba: */ d7959f8d5d 2014-07-22 kinaba: } d7959f8d5d 2014-07-22 kinaba: // END CUT HERE