cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
SRM | |
SRM492 の成績・ソース (要ログイン) : WA/WA/- : 過去最悪
あとで | |
static const LL INF = 0x1fffffffffffffffLL; template<typename T> struct DP3 { int N1, N2, N3; vector<T> data; DP3(int N1, int N2, int N3, const T& t = T()) : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); } T& operator()(int i1, int i2, int i3) { return data[ ((i1*N2)+i2)*N3+i3 ]; } void swap(DP3& rhs) { data.swap(rhs.data); } }; class TimeTravellingTour { public: long long determineCost(int N, vector <int> cities, vector <string> roads) { vector< vector<LL> > G(N, vector<LL>(N,INF)); { string str = accumulate(roads.begin(), roads.end(), string("")); for(int i=0; i<str.size(); ++i) if( str[i] == ',' ) str[i] = ' '; stringstream sin(str); for(int a,b,cost; sin>>a>>b>>cost; ) G[a][b] = G[b][a] = cost; } for(int i=0; i<N; ++i) G[i][i] = 0; for(int k=0; k<N; ++k) for(int i=0; i<N; ++i) for(int j=0; j<N; ++j) G[i][j] = min(G[i][j], G[i][k]+G[k][j]); DP3<LL> memo(N, cities.size()+1, cities.size()+1, -1); LL a = rec( 0, 0, cities.size(), cities, G, memo ); return a>=INF ? -1 : a; } LL rec(int cur, int s, int e, const vector<int>& C, const vector< vector<LL> >& G, DP3<LL>& memo ) { if( s+1 == e ) return G[cur][C[s]]; if( memo(cur,s,e) >= 0 ) return memo(cur,s,e); LL best = INF; for(int v=0; v<G[cur].size(); ++v) if( G[cur][v] < INF ) for(int m=s+1; m<e; ++m) best = min(best, G[cur][v]+rec(v,s,m,C,G,memo)+rec(v,m,e,C,G,memo)); return memo(cur,s,e) = best; } };
あとで | |
typedef complex<double> CMP; double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); } double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); } int ccw(const CMP& a, CMP b, CMP c) { b -= a; c -= a; if( outer_prod(b,c) > 0 ) return +1; // counter clockwise if( outer_prod(b,c) < 0 ) return -1; // clockwise if( inner_prod(b,c) < 0 ) return +2; // c--[a--b] on line if( norm(b) < norm(c) ) return -2; // [a--b]--c on line return 0; // [a--c--b] on line } class TimeTravellingGardener { public: int determineUsage(vector <int> distance, vector <int> height) { const int N = height.size(); distance.insert(distance.begin(), 0); partial_sum(distance.begin(), distance.end(), distance.begin()); vector<CMP> p; for(int i=0; i<N; ++i) p.push_back( CMP(distance[i], height[i]) ); int best = N-1; for(int i=0; i<N; ++i) for(int j=i+1; j<N; ++j) { best = min(best, score(p[i], p[j], p)); best = min(best, score(p[i].real(), p[j], p)); best = min(best, score(p[i], p[j].real(), p)); } return best; } int score(const CMP& a, const CMP& b, const vector<CMP>& p) { int s = 0; for(int i=0; i<p.size(); ++i) { if( ccw(a, b, p[i]) == -1 ) return INT_MAX; if( ccw(a, b, p[i].real()) == +1 ) return INT_MAX; if( ccw(a, b, p[i]) == +1 ) ++s; } return s; } };
presented by
cafelier/k.inaba
under
