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) > 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 > 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() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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, > 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, > 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)< > 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& > 61 if(prev_s<4) { > 62 s = prev_s + 1; > 63 dp(i,s) = max(dp(i,s), dp(i-1,prev_s) + > 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) > 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 > 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() > 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 > 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() > 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| > 90 // CAUTION: ENSURE s1 and s2 NOT be included on dp-on-tree and | > 91 // otherwise C(N, |s1|) will fix the timing s1 is filled, which > 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) > 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 > 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() > 109 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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