cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
SRM | |
SRM Member Pilot 2 の成績・ソース（要ログイン） : AC/WA/WA : 撃墜ラッシュ
あとで | |
都市１個の場合への対処。あと、最初 airportCost*N から始めて、つながるたびに -=airportCost していくルーチンだと精度が足りてなかった。airportCost*その時のサイズ、を毎回計算する様に。以外といろんなとこがボロボロだな…
あと、TZTester改から空のテストケースを２個生成して、埋めないとコンパイル通らないようにして挑むようにしました。これくらいしないと僕はいつまでもコーナーケースを忘れ続ける。
struct UnionFind { vector<int> uf, sz; int nc; UnionFind(int N): uf(N), sz(N,1), nc(N) { for(int i=0; i<N; ++i) uf[i] = i; } int size() { return nc; } int Find(int a) { return uf[a]==a ? a : uf[a]=Find(uf[a]); } bool Union(int a, int b) { a = Find(a); b = Find(b); if( a != b ) { if( sz[a] >= sz[b] ) swap(a, b); uf[a] = b; sz[b] += sz[a]; --nc; } return (a!=b); } }; class TransportationNetwork { public: double minCost(vector <int> cityX, vector <int> cityY, double roadCost, double airportCost) { const int N = cityX.size(); if( N == 1 ) return 0.0; typedef pair<int,int> edge; typedef pair<double,edge> cedge; priority_queue< cedge, vector<cedge>, greater<cedge> > Q; for(int i=0; i<N; ++i) for(int j=i+1; j<N; ++j) { double L = hypot(cityX[i]-cityX[j], cityY[i]-cityY[j]); Q.push( cedge(roadCost*L, edge(i,j)) ); } UnionFind uf(N); double curCost = 0; double minCost = airportCost*N; while( !Q.empty() ) { double c = Q.top().first; int a = Q.top().second.first; int b = Q.top().second.second; Q.pop(); if( uf.Union(a,b) ) { curCost += c; minCost = min(minCost, curCost + (uf.size()<=1 ? 0 : uf.size())*airportCost); } } return minCost; } };
あとで | |
tsukunoさんにおしえてもらった。十分シンプルなダイナミック計画法であった…。
class PrefixFreeCode { public: int solve(int N, const vector<int>& C) { // The best way to assign N codes to the codetree // whose root edges are C[i..$]. // special cases: // n==1 && i==0 => cost 0 (assign to the root) // n==0 => cost 0 // n==0 && i==$ => cost 0 (for this, allocate C.size()+1 as sentinels) vector< vector<int> > dp(N+1, vector<int>(C.size()+1, 0)); for(int n=1; n<=N; ++n) for(int i=(n==1 ? 1 : 0); i<C.size(); ++i) { const int at_least = (i==C.size()-1 ? n : 1); const int at_most = (i==0 ? n-1 : n); int result = INT_MAX; for(int k=at_least; k<=at_most; ++k) result = min(result, dp[k][0]+C[i]*k + dp[n-k][i+1]); dp[n][i] = result; } return dp[N][0]; } int minCost(int N, vector <int> characterCosts) { sort(characterCosts.begin(), characterCosts.end()); return solve(N, characterCosts); } };
presented by
cafelier/k.inaba
under
