Overview
| SHA1 Hash: | 42f877f59c4b8acb85c481dc1891d88e8fd56e4c |
|---|---|
| Date: | 2012-12-21 10:45:08 |
| User: | kinaba |
| Comment: | 565 |
| 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/565-U/1A.cpp version [c17de3541670aa7b]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class MonstersValley { public: > 23 int minimumPrice(vector<long long> dread, vector <int> price) > 24 { > 25 const int N = dread.size(); > 26 > 27 map<int, LL> p2maxd; > 28 p2maxd[0] = 0; > 29 > 30 for(int i=0; i<N; ++i) { > 31 map<int,LL> neo; > 32 for(map<int,LL>::iterator it=p2maxd.begin(); it!=p2maxd. > 33 { > 34 int p = it->first; > 35 LL md = it->second; > 36 if( md >= dread[i] ) > 37 neo[p] = max(neo[p], md); > 38 p += price[i]; > 39 md += dread[i]; > 40 neo[p] = max(neo[p], md); > 41 } > 42 p2maxd.swap(neo); > 43 } > 44 > 45 return p2maxd.begin()->first; > 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 int& Expected, const int& Received) { > 58 bool ok = (Expected == Received); > 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(_, MonstersValley().minimumPrice(dread, price));} > 63 int main(){ > 64 > 65 CASE(0) > 66 long long dread_[] = {8, 5, 10}; > 67 vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)) > 68 int price_[] = {1, 1, 2}; > 69 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 70 int _ = 2; > 71 END > 72 CASE(0) > 73 long long dread_[] = {1, 1}; > 74 vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)) > 75 int price_[] = {1, 1}; > 76 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 77 int _ = 1; > 78 END > 79 CASE(1) > 80 long long dread_[] = {1, 2, 4, 1000000000}; > 81 vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)) > 82 int price_[] = {1, 1, 1, 2}; > 83 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 84 int _ = 5; > 85 END > 86 CASE(2) > 87 long long dread_[] = {200, 107, 105, 206, 307, 400}; > 88 vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)) > 89 int price_[] = {1, 2, 1, 1, 1, 2}; > 90 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 91 int _ = 2; > 92 END > 93 CASE(3) > 94 long long dread_[] = {5216, 12512, 613, 1256, 66, 17202, 30000, 23512, 2 > 95 vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)) > 96 int price_[] = {2, 2, 1, 1, 1, 1, 2, 1, 2, 1}; > 97 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 98 int _ = 5; > 99 END > 100 /* > 101 CASE(4) > 102 long long dread_[] = ; > 103 vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)) > 104 int price_[] = ; > 105 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 106 int _ = ; > 107 END > 108 CASE(5) > 109 long long dread_[] = ; > 110 vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)) > 111 int price_[] = ; > 112 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 113 int _ = ; > 114 END > 115 */ > 116 } > 117 // END CUT HERE
Added SRM/565-U/1B.cpp version [efa7784af0c0c530]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class TheDivisionGame { public: > 23 long long countWinningIntervals(int L, int R) > 24 { > 25 // eratos --------------------------------- > 26 vector<int> ps; > 27 { > 28 static const int N = 50000; > 29 vector<bool> isp(N+1, true); > 30 for(int p=2; p<=N; ++p) > 31 if( isp[p] ) { > 32 ps.push_back(p); > 33 for(int q=p+p; q<=N; q+=p) > 34 isp[q] = false; > 35 } > 36 } > 37 > 38 // prime decomposition -------------------- > 39 vector< vector<int> > pd(R-L+1); > 40 vector<int> rm(R-L+1); > 41 for(int v=L; v<=R; ++v) > 42 rm[v-L] = v; > 43 > 44 for(int i=0; i<ps.size(); ++i) > 45 { > 46 int p = ps[i]; > 47 for(int q=(L+p-1)/p*p; q<=R; q+=p) > 48 { > 49 int& r = rm[q-L]; > 50 int qn = 0; > 51 while(r%p==0) qn++, r/=p; > 52 pd[q-L].push_back(qn); > 53 } > 54 } > 55 > 56 for(int v=L; v<=R; ++v) > 57 if(rm[v-L] > 1) > 58 pd[v-L].push_back(1); > 59 > 60 // grundy ------------------------------------ > 61 vector<int> nim; > 62 for(int i=0; i<pd.size(); ++i) { > 63 nim.push_back(nim_calc(pd[i])); > 64 } > 65 > 66 // xorsum ------------------------------------ > 67 vector<int> sum; > 68 map<int, LL> hist; > 69 sum.push_back(0); > 70 hist[sum.back()] ++; > 71 for(int i=0; i<nim.size(); ++i) { > 72 sum.push_back(sum.back() ^ nim[i]); > 73 hist[sum.back()] ++; > 74 } > 75 > 76 LL lose = 0; > 77 for(map<int,LL>::iterator it=hist.begin(); it!=hist.end(); ++it) > 78 lose += it->second * (it->second-1) / 2; > 79 LL w = R-L+2; > 80 LL total = w*(w-1)/2; > 81 return total - lose; > 82 } > 83 > 84 int nim_calc(vector<int> sig) > 85 { > 86 if( sig.empty() ) > 87 return 0; > 88 int v = sig[0]; > 89 for(int i=1; i<sig.size(); ++i) > 90 v = merge(v, sig[i]); > 91 return v; > 92 } > 93 > 94 map<pair<int,int>, int> memo; > 95 int merge(int a, int b) > 96 { > 97 if(a>b) swap(a,b); > 98 if(a==0) > 99 return b; > 100 pair<int,int> key(a,b); > 101 if(memo.count(key)) > 102 return memo[key]; > 103 > 104 vector<bool> used; > 105 for(int x=0; x<=a; ++x) > 106 for(int y=0; y<=b; ++y) > 107 if(x!=a || y!=b) > 108 { > 109 int k = merge(x, y); > 110 if(used.size()<=k) used.resize(k+1); > 111 used[k] = true; > 112 } > 113 > 114 used.push_back(false); > 115 return memo[key] = find(used.begin(), used.end(), false) - used. > 116 } > 117 }; > 118 > 119 // BEGIN CUT HERE > 120 #include <ctime> > 121 double start_time; string timer() > 122 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 123 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 124 { os << "{ "; > 125 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 126 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 127 void verify_case(const long long& Expected, const long long& Received) { > 128 bool ok = (Expected == Received); > 129 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 130 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 131 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 132 #define END verify_case(_, TheDivisionGame().countWinningIntervals(L, R));} > 133 int main(){ > 134 CASE(0) > 135 int L = 9; > 136 int R = 10; > 137 long long _ = 2LL; > 138 END > 139 CASE(1) > 140 int L = 2; > 141 int R = 5; > 142 long long _ = 9LL; > 143 END > 144 CASE(2) > 145 int L = 2; > 146 int R = 6; > 147 long long _ = 13LL; > 148 END > 149 CASE(3) > 150 int L = 2; > 151 int R = 100; > 152 long long _ = 4345LL; > 153 END > 154 CASE(4) > 155 int L = 12566125; > 156 int R = 12567777; > 157 long long _ = 1313432LL; > 158 END > 159 CASE(5) > 160 int L = 1000000000; > 161 int R = 1001000000; > 162 long long _ = -1LL; > 163 END > 164 CASE(6) > 165 int L = 2; > 166 int R = 2; > 167 long long _ = 0LL; > 168 END > 169 CASE(6) > 170 int L = 2; > 171 int R = 3; > 172 long long _ = 0LL; > 173 END > 174 CASE(6) > 175 int L = 2; > 176 int R = 4; > 177 long long _ = 3LL; > 178 END > 179 CASE(6) > 180 int L = 4; > 181 int R = 4; > 182 long long _ = 1LL; > 183 END > 184 > 185 } > 186 // END CUT HERE
Modified lib/doc/nim.txt from [5e1e68bb34c03f9d] to [afa6596dc04e5d36].
1 // SRM338 Div1 LV3 1 // SRM338 Div1 LV3 2 2 3 定理のステートメント < > 3 -------------------------------------------------------------------------------- > 4 対象となるゲーム > 5 - 二人ゲーム > 6 - 二人とも動かせる手の集合は同じ > 7 - 動かせなくなった方が負け > 8 - 無限ループしない > 9 > 10 nim > 11 - n 個の石の山がある > 12 - 一手で 1 ～ n 個取っていい > 13 - 最後の石を取った方が勝ち（石がなくなって打つ手が無なった方が負け） > 14 > 15 *n をサイズ n の山が1個だけの nim とする > 16 - *0 は負け > 17 - *n は勝ち n>=1 > 18 > 19 -------------------------------------------------------------------------------- > 20 ゲーム > 21 - 状態 G から打てる手で遷移する先を G1, ..., Gk とする > 22 G = {G1, ..., Gk} と書く > 23 > 24 ゲームの和 > 25 - G1 + G2 を、G1 と G2 の二つのゲームがあって、どちらかをんで一手進められるゲームとする。 > 26 すなわち G1 + G2 = {(v,G2) | v∈G1} ∪ {(G1,u) | u∈G2} > 27 > 28 等価 > 29 - 二つのゲームG, Fが等価なことを G ≡ F と書く > 30 等価というのは勝ち負け一致よりもっと強い。二つのゲムの和 G+F が必敗になること。 > 31 たとえば *n と *n は同サイズの山2つのnimは必敗なので等。同サイズでなければ必勝なので等価でない > 32 等価というのは可能な動きの構造がisomorphic/bisimilarといよりは弱い。 > 33 たとえば以下で示すように *1 + *3 ≡ *2 だが初手のパターン数など違う。 > 34 > 35 -------------------------------------------------------------------------------- > 36 定理：等価(和を取ると必敗) => 勝ち負け一致 > 37 - 必勝ゲーム+必敗ゲーム なら初手で必勝を必敗に変えてにその状態を保てば勝てる。 > 38 ゆえに勝ち負けが一致しないなら和をとったゲームは必。 > 39 必敗 + 必敗 = 必敗 > 40 必勝 + 必敗 = 必勝 > 41 > 42 注意： > 43 必勝 + 必勝 = 必敗 > 44 は成り立たない！ *2 + *1 は 初手で *1 + *1 に行けるのでこれは勝てる > 45 > 46 補題：G+G は必敗 > 47 - まねっこmoveをされると負けるしかない > 48 > 49 補題：A≡B ならば A+C≡B+C > 50 - A+C+B+C = (A+B)+(C+C) = 必敗+必敗 = 必敗 > 51 > 52 補題：A≡B ならば {A,G1,G2,...}≡{B,G1,G2,...} > 53 - {A,G1,G2,...}+{B,G1,G2,...} は必敗。なぜならこちらがどう動しても > 54 A+B, G1+G1, G2+G2, ... のいずれかの必敗状態に遷移させられから。 > 55 > 56 -------------------------------------------------------------------------------- > 57 定理【ゲームの和はxor】 > 58 - *n1 + *n2 = *(n1 xor n2) > 59 - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) > 60 > 61 証明 > 62 - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 4 63 5 対象となるゲーム < 6 - 二人ゲーム < 7 - 二人とも動かせる手の集合は同じ < 8 - 動かせなくなった方が負け < 9 - 無限ループしない < > 64 10 65 11 nim < > 66 -------------------------------------------------------------------------------- 12 - サイズ s1, s2, .., sk の山がある | 67 定理【ゲームの状態遷移はmex】 13 - どれか一つ山を選んで 1 ～ 山サイズ の任意個取り除ける | 68 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 14 - 最後の山を取った方が勝ち（山がなくなって打つ手が無くなった方が負け） | 69 where mex(S) = min(nat \setminus S) 15 70 16 *n をサイズ n の山が1個だけの nim とする | 71 - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 17 - *0 は負け | 72 帰納的に、全てのゲームはなんらかの *n と等価 18 - *n は勝ち n>=1 < 19 < 20 ゲーム < 21 - 状態 G から打てる手で遷移する先を G1, ..., Gk とする < 22 G = {G1, ..., Gk} と書く < 23 73 24 等価 < > 74 証明 25 - 二つのゲームG, Fが等価なことを G ≡ F と書く | 75 - {*n1, ..., *nk} は *mex(n1,...,nk) と等価。 26 等価というのは勝ち負け一致よりもっと強い。二つのゲームの和を取ると必敗なること | 76 つまり和を取ると必敗 27 *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない | 77 *mex(n1,...,nk) 側を動かした場合、相手は対応する ni に遷移する。 > 78 {*ni} 側を mex(n1,...,nk) より小さいゲームに動かした場合mex側を対応する値に変える。 > 79 {*ni} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。 > 80 で両側等価を保ててしまう。 > 81 28 82 29 定理 < > 83 -------------------------------------------------------------------------------- 30 - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) | 84 まとめ 31 where mex(S) = min(nat \setminus S) < 32 帰納的に、全てのゲームはなんらかの *n と等価 < 33 < 34 定理の証明 < 35 - {G1, ..., Gk} は *mex(n1,...,nk) と等価。 < 36 つまり和を取ると必敗。 < 37 *mex(n1,...,nk) 側を動かした場合、相手は対応する Gi に移する。 < 38 {G} 側を mex(n1,...,nk) より小さいゲームに動かした場合mex側を対応する値に変える。 < 39 {G} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。 < 40 で両側等価を保ててしまう。 < 41 < 42 等価(和を取ると必敗) => 勝ち負け一致 の証明 < 43 - 偶奇を考えれば良い。必勝ゲーム+必敗ゲーム なら初で必勝を必敗に変えて常にその状態を < 44 保てば勝てる。ゆえに一致しないなら和をとったゲームは必勝。 < 45 85 46 < > 86 ・一手動かした次の局面が *n1 または *n2 または ... なゲー 47 まけ | 87 {*n1, ..., *nk} = *mex(n1, ..., nk) 48 @G を G のnim値とする。つまりG≡*@G | 88 ・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム 49 G = X + Y ならば @G = @X xor @Y | 89 *n1 + *n2 = *(n1 xor n2) 50 山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいのと同じ原理。 | 90 ・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム > 91 *n1 <+> *n2 = *(n1 + n2) //単に１個の山なのとかわらない > 92 ・両方一手ずつ進めるゲーム？ > 93 *n1 X *n2 = ?