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.end(); ++it) 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) << " 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 int& Expected, const int& Received) { 58 + bool ok = (Expected == Received); 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(_, 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, 2125, 33333}; 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.begin(); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 130 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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 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 12 - - サイズ s1, s2, .., sk の山がある 13 - - どれか一つ山を選んで 1 ～ 山サイズ の任意個取り除ける 14 - - 最後の山を取った方が勝ち（山がなくなって打つ手が無くなった方が負け） 66 +------------------------------------------------------------------------------------------- 67 +定理【ゲームの状態遷移はmex】 68 + - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 69 + where mex(S) = min(nat \setminus S) 15 70 16 - *n をサイズ n の山が1個だけの nim とする 17 - - *0 は負け 18 - - *n は勝ち n>=1 19 - 20 - ゲーム 21 - - 状態 G から打てる手で遷移する先を G1, ..., Gk とする 22 - G = {G1, ..., Gk} と書く 71 + - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 72 + 帰納的に、全てのゲームはなんらかの *n と等価 23 73 24 - 等価 25 - - 二つのゲームG, Fが等価なことを G ≡ F と書く 26 - 等価というのは勝ち負け一致よりもっと強い。二つのゲームの和を取ると必敗になること 27 - *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない 74 + 証明 75 + - {*n1, ..., *nk} は *mex(n1,...,nk) と等価。 76 + つまり和を取ると必敗。 77 + *mex(n1,...,nk) 側を動かした場合、相手は対応する ni に遷移する。 78 + {*ni} 側を mex(n1,...,nk) より小さいゲームに動かした場合、mex側を対応する値に変える。 79 + {*ni} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。 80 + で両側等価を保ててしまう。 81 + 28 82 29 - 定理 30 - - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) 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 - 保てば勝てる。ゆえに一致しないなら和をとったゲームは必勝。 83 +------------------------------------------------------------------------------------------- 84 +まとめ 45 85 46 - 47 -おまけ 48 - @G を G のnim値とする。つまりG≡*@G 49 - G = X + Y ならば @G = @X xor @Y 50 - 山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいのと同じ原理。 86 +・一手動かした次の局面が *n1 または *n2 または ... なゲーム 87 + {*n1, ..., *nk} = *mex(n1, ..., nk) 88 +・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム 89 + *n1 + *n2 = *(n1 xor n2) 90 +・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム 91 + *n1 <+> *n2 = *(n1 + n2) //単に１個の山なのとかわらない 92 +・両方一手ずつ進めるゲーム？ 93 + *n1 X *n2 = ?