Overview
| SHA1 Hash: | 9ce62cec1c08497bf3c27a79e7faa062ec68a198 |
|---|---|
| Date: | 2015-03-26 03:24:12 |
| User: | kinaba |
| Comment: | 654 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/654-U/1A.cpp version [b64dedb5d55d1caf]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +#include <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class SquareScores { public: 23 + double calcexpectation(vector <int> p, string s) 24 + { 25 + double ans = 0.0; 26 + for(int k=0; k<s.size(); ++k) { 27 + int num_q = 0; 28 + char ch = '*'; 29 + for(int e=k; e<s.size(); ++e) { 30 + if(s[e]=='?') 31 + num_q++; 32 + if(ch == '*') { 33 + if(s[e] != '?') 34 + ch = s[e]; 35 + } else { 36 + if(s[e] != '?' && s[e] != ch) 37 + break; 38 + } 39 + 40 + for(int ci=0; ci<p.size(); ++ci) 41 + if(ch=='*' || ch-'a'==ci) 42 + ans += pow(p[ci]/100.0, num_q); 43 + } 44 + } 45 + return ans; 46 + } 47 +}; 48 + 49 +// BEGIN CUT HERE 50 +#include <ctime> 51 +double start_time; string timer() 52 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 53 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 54 + { os << "{ "; 55 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 56 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 57 +void verify_case(const double& Expected, const double& Received) { 58 + bool ok = (abs(Expected - Received) < 1e-9); 59 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 60 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 61 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 62 +#define END verify_case(_, SquareScores().calcexpectation(p, s));} 63 +int main(){ 64 + 65 +CASE(0) 66 + int p_[] = {1, 99}; 67 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 68 + string s = "aaaba"; 69 + double _ = 8.0; 70 +END 71 +CASE(1) 72 + int p_[] = {10, 20, 70}; 73 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 74 + string s = "aa?bbbb"; 75 + double _ = 15.0; 76 +END 77 +CASE(2) 78 + int p_[] = {10, 20, 30, 40}; 79 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 80 + string s = "a??c?dc?b"; 81 + double _ = 11.117; 82 +END 83 +CASE(3) 84 + int p_[] = {25, 25, 21, 2, 2, 25}; 85 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 86 + string s = "a??b???????ff??e"; 87 + double _ = 21.68512690712425; 88 +END 89 +CASE(4) 90 + int p_[] = {4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 3, 4, 4, 4}; 91 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 92 + string s = "??????????????????????????????"; 93 + double _ = 31.16931963781721; 94 +END 95 +CASE(5) 96 + int p_[] = {4, 3, 4, 3, 8, 2, 4, 3, 4, 4, 3, 2, 4, 4, 3, 4, 2, 4, 7, 6, 4, 4, 3, 4, 4, 3}; 97 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 98 + string s = "makigotapresentfromniko"; 99 + double _ = 23.0; 100 +END 101 +/* 102 +CASE(6) 103 + int p_[] = ; 104 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 105 + string s = ; 106 + double _ = ; 107 +END 108 +CASE(7) 109 + int p_[] = ; 110 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 111 + string s = ; 112 + double _ = ; 113 +END 114 +*/ 115 +} 116 +// END CUT HERE
Added SRM/654-U/1B.cpp version [130fb986bddece45]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +#include <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 + 21 +template<typename T> 22 +struct DP2 23 +{ 24 + const int N1, N2; 25 + vector<T> data; 26 + DP2(int N1, int N2, const T& t = T()) 27 + : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<28)); } 28 + T& operator()(int i1, int i2) 29 + { return data[ (i1*N2)+i2 ]; } 30 + void swap(DP2& rhs) 31 + { data.swap(rhs.data); } 32 +}; 33 + 34 +class SuccessiveSubtraction2 { public: 35 + vector <int> calc(vector <int> a, vector <int> p, vector <int> v) 36 + { 37 + vector<int> answer; 38 + for(int i=0; i<p.size(); ++i) { 39 + a[p[i]] = v[i]; 40 + 41 + if(a.size() == 1) { 42 + answer.push_back(a[0]); 43 + continue; 44 + } 45 + 46 + answer.push_back(a[0]-a[1]+solve(a)); 47 + } 48 + return answer; 49 + } 50 + 51 + int solve(const vector<int>& a) 52 + { 53 + DP2<int> dp(a.size(), 5, -0x1fffffff); 54 + dp(1, 0) = 0; 55 + 56 + for(int i=2; i<a.size(); ++i) 57 + for(int prev_s=0; prev_s<=4; ++prev_s) 58 + { 59 + int s = prev_s; 60 + dp(i,s) = max(dp(i,s), dp(i-1,prev_s) + a[i]*(s&1 ? +1 : -1)); 61 + if(prev_s<4) { 62 + s = prev_s + 1; 63 + dp(i,s) = max(dp(i,s), dp(i-1,prev_s) + a[i]*(s&1 ? +1 : -1)); 64 + } 65 + } 66 + 67 + int best = 0; 68 + for(int s=0; s<=4; ++s) 69 + best = max(best, dp(a.size()-1, s)); 70 + return best; 71 + } 72 +}; 73 + 74 +// BEGIN CUT HERE 75 +#include <ctime> 76 +double start_time; string timer() 77 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 78 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 79 + { os << "{ "; 80 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 81 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 82 +void verify_case(const vector <int>& Expected, const vector <int>& Received) { 83 + bool ok = (Expected == Received); 84 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 85 + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 86 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 87 +#define END verify_case(_, SuccessiveSubtraction2().calc(a, p, v));} 88 +int main(){ 89 + 90 +CASE(0) 91 + int a_[] = {1, 2, 3, 4, 5}; 92 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 93 + int p_[] = {1, 2, 0, 4, 3}; 94 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 95 + int v_[] = {3, 9, -10, 5, 1}; 96 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 97 + int __[] = {10, 16, 5, 5, 2 }; 98 + vector <int> _(__, __+sizeof(__)/sizeof(*__)); 99 +END 100 +CASE(1) 101 + int a_[] = {-100, -100, -100, -100, -100}; 102 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 103 + int p_[] = {0, 1, 2, 3, 4}; 104 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 105 + int v_[] = {0, 0, 0, 0, 0}; 106 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 107 + int __[] = {400, 300, 200, 100, 0 }; 108 + vector <int> _(__, __+sizeof(__)/sizeof(*__)); 109 +END 110 +CASE(2) 111 + int a_[] = {83, 0, 25, 21}; 112 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 113 + int p_[] = {0, 3, 2, 1, 3, 1, 2}; 114 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 115 + int v_[] = {10, -90, 33, 52, -100, 0, 45}; 116 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 117 + int __[] = {56, 125, 133, 81, 91, 143, 155 }; 118 + vector <int> _(__, __+sizeof(__)/sizeof(*__)); 119 +END 120 +CASE(3) 121 + int a_[] = {1}; 122 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 123 + int p_[] = {0, 0, 0, 0}; 124 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 125 + int v_[] = {10, -10, 100, -100}; 126 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 127 + int __[] = {10, -10, 100, -100 }; 128 + vector <int> _(__, __+sizeof(__)/sizeof(*__)); 129 +END 130 +CASE(4) 131 + int a_[] = {-11, -4, 28, 38, 21, -29, -45, 11, -58, -39, 92, 35, -56, -6, 29, -2, 61, 10, -29, -63}; 132 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 133 + int p_[] = {19, 5, 3, 10, 4, 18, 5, 2, 0, 15}; 134 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 135 + int v_[] = {-19, 21, 7, -66, 38, -39, -22, 24, -32, 13}; 136 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 137 + int __[] = {451, 443, 412, 440, 457, 467, 468, 464, 443, 458 }; 138 + vector <int> _(__, __+sizeof(__)/sizeof(*__)); 139 +END 140 +CASE(5) 141 +int a_[] = {10, 20}; 142 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 143 + int p_[] = {0, 1}; 144 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 145 + int v_[] = {2, 3}; 146 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 147 + int __[] = {-18, -1}; 148 + vector <int> _(__, __+sizeof(__)/sizeof(*__)); 149 +END 150 +/* 151 +CASE(6) 152 + int a_[] = ; 153 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 154 + int p_[] = ; 155 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 156 + int v_[] = ; 157 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 158 + int __[] = ; 159 + vector <int> _(__, __+sizeof(__)/sizeof(*__)); 160 +END 161 +*/ 162 +} 163 +// END CUT HERE
Added SRM/654-U/1C-U.cpp version [9917d60b47bafaf7]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +#include <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +static const unsigned MODVAL = 1000000007; 23 +struct mint 24 +{ 25 + unsigned val; 26 + mint():val(0){} 27 + mint(int x):val(x%MODVAL) {} 28 + mint(unsigned x):val(x%MODVAL) {} 29 + mint(LL x):val(x%MODVAL) {} 30 +}; 31 +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 32 +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } 33 +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 34 +mint operator+(mint x, mint y) { return x+=y; } 35 +mint operator-(mint x, mint y) { return x-=y; } 36 +mint operator*(mint x, mint y) { return x*=y; } 37 + 38 +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } 39 +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } 40 +mint operator/(mint x, mint y) { return x/=y; } 41 + 42 +vector<mint> FAC_(1,1); 43 +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[size_t(n)]; } 44 + 45 +vector< vector<mint> > CP_; 46 +mint C(int n, int k) { 47 + while( CP_.size() <= n ) { 48 + int nn = CP_.size(); 49 + CP_.push_back(vector<mint>(nn+1,1)); 50 + for(int kk=1; kk<nn; ++kk) 51 + CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 52 + } 53 + return k<0 || n<k ? 0 : CP_[n][k]; 54 +} 55 + 56 +class TwoEntrances { public: 57 + int count(vector <int> a, vector <int> b, int s1, int s2) 58 + { 59 + const int N = a.size() + 1; 60 + 61 + // Graph 62 + vector<vector<int>> g(N); 63 + for(int i=0; i<a.size(); ++i) { 64 + g[a[i]].push_back(b[i]); 65 + g[b[i]].push_back(a[i]); 66 + } 67 + 68 + // Tree (as root=s1) 69 + vector<vector<int>> children(N); 70 + vector<int> parent(N, -1); 71 + vector<int> tree_size(N); 72 + function<int(int,int)> rec; rec = [&](int pre, int v) { 73 + int sub_size = 1; 74 + for(auto u: g[v]) if(u != pre) { 75 + children[v].push_back(u); 76 + parent[u] = v; 77 + sub_size += rec(v, u); 78 + } 79 + tree_size[v] = sub_size; 80 + }; 81 + rec(-1, s1); 82 + 83 + // Mark s1--s2 84 + vector<bool> s2_path(N); 85 + for(int v=s2; v!=-1; v=parent[v]) 86 + s2_path[v] = true; 87 + 88 + // Parts except s1--s2 path is easy. 89 + // It's dp-on-tree[s1 \setminus s2] * dp-on-tree[s1] * C(N, |s1|) * C(N-|s1|, |s2|). 90 + // CAUTION: ENSURE s1 and s2 NOT be included on dp-on-tree and |s|. 91 + // otherwise C(N, |s1|) will fix the timing s1 is filled, which reduces the freedom in 92 + // path mode. 93 + 94 + // What about the rest N-|s1|-|s2|? 95 + } 96 +}; 97 + 98 +// BEGIN CUT HERE 99 +#include <ctime> 100 +double start_time; string timer() 101 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 102 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 103 + { os << "{ "; 104 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 105 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 106 +void verify_case(const int& Expected, const int& Received) { 107 + bool ok = (Expected == Received); 108 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 109 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 110 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 111 +#define END verify_case(_, TwoEntrances().count(a, b, s1, s2));} 112 +int main(){ 113 + 114 +CASE(0) 115 + int a_[] = {0, 1, 2}; 116 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 117 + int b_[] = {1, 2, 3}; 118 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 119 + int s1 = 0; 120 + int s2 = 1; 121 + int _ = 4; 122 +END 123 +CASE(1) 124 + int a_[] = {0, 1, 2}; 125 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 126 + int b_[] = {1, 2, 3}; 127 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 128 + int s1 = 0; 129 + int s2 = 2; 130 + int _ = 9; 131 +END 132 +CASE(2) 133 + int a_[] = {0, 1, 1, 3, 3, 3, 6, 7, 6}; 134 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 135 + int b_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 136 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 137 + int s1 = 1; 138 + int s2 = 9; 139 + int _ = 16000; 140 +END 141 +CASE(3) 142 + int a_[] = {0, 0, 1, 2, 3, 1, 2, 0, 6, 5, 10, 10}; 143 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 144 + int b_[] = {1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10, 11, 12}; 145 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 146 + int s1 = 3; 147 + int s2 = 6; 148 + int _ = 310464; 149 +END 150 +CASE(4) 151 + int a_[] = {0}; 152 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 153 + int b_[] = {1}; 154 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 155 + int s1 = 1; 156 + int s2 = 0; 157 + int _ = 2; 158 +END 159 +/* 160 +CASE(5) 161 + int a_[] = ; 162 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 163 + int b_[] = ; 164 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 165 + int s1 = ; 166 + int s2 = ; 167 + int _ = ; 168 +END 169 +CASE(6) 170 + int a_[] = ; 171 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 172 + int b_[] = ; 173 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 174 + int s1 = ; 175 + int s2 = ; 176 + int _ = ; 177 +END 178 +*/ 179 +} 180 +// END CUT HERE