cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
SRM | |
SRM491 の成績・ソース (要ログイン) : AC/-/- : ちょっと難しいセットになるとすぐこの成績ですよもうだめだ
あとで | |
class PrefixTree { public: static vector<int> wordToFreq( const string& word ) { vector<int> freq(26); for(int i=0; i<word.size(); ++i) freq[word[i]-'a']++; return freq; } static vector< vector<int> > wordsToFreqs( const vector<string>& words ) { vector< vector<int> > freqs; transform(words.begin(), words.end(), back_inserter(freqs), &wordToFreq); return freqs; } static int commonPrefix(const vector< vector<int> >& freqs, int s) { vector<int> common; for(int first=1,i=0; (1<<i)<=s; ++i) if( s & (1<<i) ) if( first ) { common = freqs[i]; first = 0; } else { for(int k=0; k<26; ++k) common[k] = min(common[k], freqs[i][k]); } return accumulate(common.begin(), common.end(), 0); } int getNumNodes(vector<string> words) { const int N = words.size(); const vector< vector<int> >& freqs = wordsToFreqs(words); vector<int> dp(1<<N); for(int s=1; s<(1<<N); ++s) { dp[s] = 1; for(int i=0; i<N; ++i) if( s & (1<<i) ) dp[s] += words[i].size(); int cp = commonPrefix(freqs, s); for(int ss=s-1; ss&=s; --ss) dp[s] = min(dp[s], dp[ss]+dp[s&~ss]-cp-1); } return dp[(1<<N)-1]; } };
あとで | |
template<typename T> class IdGen { map<T, int> v2id_; vector<T> id2v_; public: int v2id(const T& v) { if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } return v2id_[v]; } const T& id2v(int i) const { return id2v_[i]; } int size() const { return id2v_.size(); } }; template<typename Vert, typename Cost, typename Flow, int NV=256> class MinCostFlow { IdGen<Vert> idgen; vector<int> G[NV]; Flow F[NV][NV]; Cost C[NV][NV]; public: void addEdge( Vert s_, Vert t_, Cost c, Flow f ) { int s = idgen.v2id(s_), t = idgen.v2id(t_); G[s].push_back(t); G[t].push_back(s); C[s][t] = c; C[t][s] = -c; F[s][t] = f; F[t][s] = 0; } pair<Cost, Flow> calc( Vert s_, Vert t_ ) { const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_); static const Cost COST_INF = 1e+300; // !!EDIT HERE!! static const Flow FLOW_INF = 0x7fffffff; Cost total_cost = 0; Flow total_flow = 0; vector<Cost> h(N, 0); // potential for(Flow RF=FLOW_INF; RF>0; ) // residual flow { // Dijkstra -- find the min-cost path vector<Cost> d(N, COST_INF); d[S] = 0; vector<int> prev(N, -1); typedef pair< Cost, pair<int,int> > cedge; priority_queue< cedge, vector<cedge>, greater<cedge> > Q; Q.push( cedge(0, make_pair(S,S)) ); while( !Q.empty() ) { cedge e = Q.top(); Q.pop(); if( prev[e.second.second] >= 0 ) continue; prev[e.second.second] = e.second.first; int u = e.second.second; for(int i=0; i<G[u].size(); ++i) { int v = G[u][i]; Cost r_cost = C[u][v] + h[u] - h[v]; if( F[u][v] > 0 && d[v] > d[u]+r_cost ) Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) ); } } if( prev[T] < 0 ) break; // Finished // As much as possible Flow f = RF; for(int u=T; u!=S; u=prev[u]) f = min(f, F[prev[u]][u]); RF -= f; total_flow += f; for(int u=T; u!=S; u=prev[u]) { total_cost += f * C[prev[u]][u]; F[prev[u]][u] -= f; F[u][prev[u]] += f; } // Update the potential for(int u=0; u<N; ++u) h[u] += d[u]; } return make_pair(total_cost, total_flow); } }; class FoxCardGame { public: double theMaxProportion(vector <double> pileA, vector <double> pileB, int k) { double L=1, R=50; for(int i=0; i<50; ++i) (possible(pileA, pileB, k, (L+R)/2) ? L : R) = (L+R)/2; return L; } enum Tag {Src, Left, Right, Target, Goal}; bool possible(vector <double> pileA, vector <double> pileB, int k, double R) { MinCostFlow<pair<Tag,int>, double, int> mcf; for(int a=0; a<pileA.size(); ++a) mcf.addEdge( make_pair(Src,0), make_pair(Left,a), 0.0, 1 ); for(int a=0; a<pileA.size(); ++a) for(int b=0; b<pileB.size(); ++b) { double x_ = pileA[a]+pileB[b], y_ = pileA[a]*pileB[b]; double x = max(x_,y_), y = min(x_,y_); mcf.addEdge( make_pair(Left,a), make_pair(Right,b), R*y-x+10000.0, 1 ); } for(int b=0; b<pileB.size(); ++b) mcf.addEdge( make_pair(Right,b), make_pair(Target,0), 0.0, 1 ); mcf.addEdge( make_pair(Target,0), make_pair(Goal, 0), 0.0, k ); return mcf.calc( make_pair(Src,0), make_pair(Goal,0) ).first <= 10000.0*k; } };
presented by
cafelier/k.inaba
under
