Overview
| SHA1 Hash: | 339e20815a18bd9cbd3e788741dcfb9dc65fc0b9 |
|---|---|
| Date: | 2014-10-24 12:49:30 |
| User: | kinaba |
| Comment: | 637 |
| 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/637-U/1A.cpp version [d3e4a91d474c99ac]
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 GreaterGame { public: 23 + double calc(vector <int> hand, vector <int> sothe) 24 + { 25 + const int N = hand.size(); 26 + 27 + set<int> me, you, rest; 28 + for(int c=1; c<=2*N; ++c) rest.insert(c); 29 + for(int c: hand) me.insert(c), rest.erase(c); 30 + for(int c: sothe) you.insert(c), rest.erase(c); 31 + 32 + double ans = 0.0; 33 + while(!you.empty() && *you.rbegin()>0) 34 + { 35 + int y = *you.rbegin(); you.erase(y); 36 + 37 + auto it = me.rbegin(); 38 + if(*it > y) { 39 + while(*it>y) { 40 + auto kt = it; 41 + ++kt; 42 + if(kt==me.rend() || *kt<y) 43 + break; 44 + it = kt; 45 + } 46 + me.erase(*it); 47 + ++ans; 48 + } else { 49 + me.erase(me.begin()); 50 + } 51 + } 52 + 53 + for(int c: me) 54 + ans += count_if(rest.begin(), rest.end(), [&](int y){return y<c;}) / (double)rest.size(); 55 + return ans; 56 + } 57 +}; 58 + 59 +// BEGIN CUT HERE 60 +#include <ctime> 61 +double start_time; string timer() 62 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 63 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 64 + { os << "{ "; 65 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 66 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 67 +void verify_case(const double& Expected, const double& Received) { 68 + bool ok = (abs(Expected - Received) < 1e-9); 69 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 70 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 71 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 72 +#define END verify_case(_, GreaterGame().calc(hand, sothe));} 73 +int main(){ 74 + 75 +CASE(0) 76 + int hand_[] = {4,2}; 77 + vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 78 + int sothe_[] = {-1,-1}; 79 + vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 80 + double _ = 1.5; 81 +END 82 +CASE(1) 83 + int hand_[] = {4,2}; 84 + vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 85 + int sothe_[] = {1,3}; 86 + vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 87 + double _ = 2.0; 88 +END 89 +CASE(2) 90 + int hand_[] = {2}; 91 + vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 92 + int sothe_[] = {-1}; 93 + vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 94 + double _ = 1.0; 95 +END 96 +CASE(3) 97 + int hand_[] = {1,3,5,7}; 98 + vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 99 + int sothe_[] = {8,-1,4,-1}; 100 + vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 101 + double _ = 2.5; 102 +END 103 +CASE(4) 104 + int hand_[] = {6,12,17,14,20,8,16,7,2,15}; 105 + vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 106 + int sothe_[] = {-1,-1,4,-1,11,3,13,-1,-1,18}; 107 + vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 108 + double _ = 8.0; 109 +END 110 +/* 111 +CASE(5) 112 + int hand_[] = ; 113 + vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 114 + int sothe_[] = ; 115 + vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 116 + double _ = ; 117 +END 118 +CASE(6) 119 + int hand_[] = ; 120 + vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 121 + int sothe_[] = ; 122 + vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 123 + double _ = ; 124 +END 125 +*/ 126 +} 127 +// END CUT HERE
Added SRM/637-U/1B.cpp version [2058df9c81213c58]
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 PathGame { public: 23 + string judge(vector <string> board) 24 + { 25 + vector<int> s; 26 + for(int i=0; i<board[0].size(); ++i) 27 + s.push_back((board[0][i]=='#')+(board[1][i]=='#')*2); 28 + return firstWins(s) ? "Snuke" : "Sothe"; 29 + } 30 + 31 + bool firstWins(const vector<int>& s) 32 + { 33 + memo.assign(s.size()*10, -1); 34 + 35 + vector<int> games; 36 + 37 + int i = 0; 38 + if(s[0] == 0) 39 + { 40 + int e = find_if(s.begin()+i, s.end(), [&](int v){return v!=0;}) - s.begin(); 41 + int L = 0; 42 + int N = e-i; 43 + int R = e==s.size() ? 0 : s[e]; 44 + games.push_back(grundy(L,N,R)); 45 + i = e; 46 + } 47 + while(i < s.size()) 48 + { 49 + int L = s[i]; 50 + i = find(s.begin()+i, s.end(), 0) - s.begin(); 51 + int e = find_if(s.begin()+i, s.end(), [&](int v){return v!=0;}) - s.begin(); 52 + int N = e-i; 53 + int R = e==s.size() ? 0 : s[e]; 54 + games.push_back(grundy(L,N,R)); 55 + i = e; 56 + } 57 + 58 + return xor_all(games) != 0; 59 + } 60 + 61 + vector<int> memo; 62 + int grundy(int L, int N, int R) 63 + { 64 + if(N == 0) 65 + return 0; // no move 66 + if(N == 1) { 67 + if(L==0 || R==0 || L==R) 68 + return 1; 69 + return 0; 70 + } 71 + 72 + int key = N*9+L*3+R; 73 + if(memo[key] >= 0) 74 + return memo[key]; 75 + 76 + vector<int> next; 77 + for(int i=0; i<N; ++i) 78 + { 79 + if(i==0) { 80 + if(L!=2) next.push_back(grundy(1,N-1,R)); 81 + if(L!=1) next.push_back(grundy(2,N-1,R)); 82 + } else if(i==N-1) { 83 + if(R!=2) next.push_back(grundy(L,N-1,1)); 84 + if(R!=1) next.push_back(grundy(L,N-1,2)); 85 + } else { 86 + next.push_back(grundy(L,i,1)^grundy(1,N-i-1,R)); 87 + next.push_back(grundy(L,i,2)^grundy(2,N-i-1,R)); 88 + } 89 + } 90 + return memo[key] = mex(next); 91 + } 92 + 93 + int xor_all(const vector<int>& games) 94 + { 95 + int v = 0; 96 + for(int g: games) 97 + v ^= g; 98 + return v; 99 + } 100 + 101 + int mex(const vector<int>& games) 102 + { 103 + set<int> gs(games.begin(), games.end()); 104 + for(int v=0;; ++v) 105 + if(gs.count(v)==0) 106 + return v; 107 + } 108 +}; 109 + 110 +// BEGIN CUT HERE 111 +#include <ctime> 112 +double start_time; string timer() 113 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 114 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 115 + { os << "{ "; 116 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 117 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 118 +void verify_case(const string& Expected, const string& Received) { 119 + bool ok = (Expected == Received); 120 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 121 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 122 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 123 +#define END verify_case(_, PathGame().judge(board));} 124 +int main(){ 125 + 126 +CASE(0) 127 + string board_[] = {"#.." 128 +,"..."}; 129 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 130 + string _ = "Snuke"; 131 +END 132 +CASE(1) 133 + string board_[] = {"#" 134 +,"."}; 135 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 136 + string _ = "Sothe"; 137 +END 138 +CASE(2) 139 + string board_[] = {"....." 140 +,"..#.."}; 141 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 142 + string _ = "Sothe"; 143 +END 144 +CASE(3) 145 + string board_[] = {".#..." 146 +,"....."}; 147 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 148 + string _ = "Snuke"; 149 +END 150 +CASE(4) 151 + string board_[] = {".....#..#........##......." 152 +,"..........#..........#...."}; 153 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 154 + string _ = "Snuke"; 155 +END 156 +/* 157 +CASE(5) 158 + string board_[] = ; 159 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 160 + string _ = ; 161 +END 162 +CASE(6) 163 + string board_[] = ; 164 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 165 + string _ = ; 166 +END 167 +*/ 168 +} 169 +// END CUT HERE
Added SRM/637-U/1C-U.cpp version [0a31ef5a52a2efc2]
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 ConnectingGame { public: 23 + string isValid(vector <string> board) 24 + { 25 + return hasCuttingPaint(board) ? "invalid" : "valid"; 26 + } 27 + 28 + bool hasCuttingPaint(vector<string> board) { 29 + const int H = board.size(); 30 + const int W = board[0].size(); 31 + if(H==1 || W==1) 32 + return false; 33 + 34 + set<char> T,L,R,B; 35 + map<char, set<char>> G; 36 + 37 + for(int y=0; y<H; ++y) 38 + for(int x=0; x<W; ++x) 39 + { 40 + if(y==0) T.insert(board[y][x]); 41 + if(y==H-1) B.insert(board[y][x]); 42 + if(x==0) L.insert(board[y][x]); 43 + if(x==W-1) R.insert(board[y][x]); 44 + 45 + int dy[]={0,0,-1,+1}; 46 + int dx[]={-1,+1,0,0}; 47 + for(int d=0; d<4; ++d) { 48 + int yy=y+dy[d], xx=x+dx[d]; 49 + if(0<=yy&&yy<H&&0<=xx&&xx<W&&board[y][x]!=board[yy][xx]) 50 + G[board[y][x]].insert(board[yy][xx]); 51 + } 52 + } 53 + 54 + // Is there a way to paint nodes in G s.t. 55 + // - all L~G~R paths have at least one Blue node, and 56 + // - all T~G~B paths have at least one Red node? 57 + // |G|<=62. 58 + } 59 +}; 60 + 61 +// BEGIN CUT HERE 62 +#include <ctime> 63 +double start_time; string timer() 64 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 65 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 66 + { os << "{ "; 67 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 68 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 69 +void verify_case(const string& Expected, const string& Received) { 70 + bool ok = (Expected == Received); 71 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 72 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 73 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 74 +#define END verify_case(_, ConnectingGame().isValid(board));} 75 +int main(){ 76 + 77 +CASE(0) 78 + string board_[] = {"AAB" 79 +,"CCD"}; 80 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 81 + string _ = "invalid"; 82 +END 83 +CASE(1) 84 + string board_[] = {"AA" 85 +,"BB"}; 86 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 87 + string _ = "valid"; 88 +END 89 +CASE(2) 90 + string board_[] = {"iii" 91 +,"iwi" 92 +,"iii"}; 93 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 94 + string _ = "valid"; 95 +END 96 +CASE(3) 97 + string board_[] = {"SSnukee" 98 +,"SKnuthe" 99 +,"SSSothe"}; 100 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 101 + string _ = "invalid"; 102 +END 103 +CASE(4) 104 + string board_[] = {"rng58" 105 +,"rnggn" 106 +,"rnnnn"}; 107 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 108 + string _ = "valid"; 109 +END 110 +CASE(5) 111 + string board_[] = {"ggssGGGGGG","ggssspGGGG","ggsssppGGG","ggWsspGGGG","gggsspGGiG","g7ssspGGGG","gggsseKK33","gggssssK33","gHgsssHA33","HHHHHHHHHH","HHHHHHHHH6","HHHHHHHHb6"}; 112 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 113 + string _ = "invalid"; 114 +END 115 +/* 116 +CASE(6) 117 + string board_[] = ; 118 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 119 + string _ = ; 120 +END 121 +CASE(7) 122 + string board_[] = ; 123 + vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 124 + string _ = ; 125 +END 126 +*/ 127 +} 128 +// END CUT HERE
Modified lib/doc/nim.txt from [a6c762d68e00b3ce] to [b75bd46f8bc82eec].
6 6 - 二人とも動かせる手の集合は同じ 7 7 - 動かせなくなった方が負け 8 8 - 無限ループしない 9 9 10 10 nim 11 11 - n 個の石の山がある 12 12 - 一手で 1 ～ n 個取っていい 13 - - 最後の石を取った方が勝ち（石がなくなって打つ手が無くなった方が負け） 13 + - 石がなくなって打つ手が無くなった方が負け（最後の石を取った方が勝ち） 14 14 15 15 *n をサイズ n の山が1個だけの nim とする 16 16 - *0 は負け 17 17 - *n は勝ち n>=1 18 18 19 19 ------------------------------------------------------------------------------------------- 20 20 ゲーム ................................................................................ 23 23 24 24 ゲームの和 25 25 - G1 + G2 を、G1 と G2 の二つのゲームがあって、どちらかを選んで一手進められるゲームとする。 26 26 すなわち G1 + G2 = {(v,G2) | v∈G1} ∪ {(G1,u) | u∈G2} 27 27 28 28 等価 29 29 - 二つのゲームG, Fが等価なことを G ≡ F と書く 30 - 等価というのは勝ち負け一致よりもっと強い。二つのゲームの和 G+F が必敗になること。 30 + 等価というのは勝ち負け一致よりもっと強い。二つのゲームの和 G+F が必敗になることと定義する。 31 31 たとえば *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない 32 32 等価というのは可能な動きの構造がisomorphic/bisimilarというよりは弱い。 33 33 たとえば以下で示すように *1 + *3 ≡ *2 だが初手のパターン数など違う。 34 34 35 35 ------------------------------------------------------------------------------------------- 36 -定理：等価(和を取ると必敗) => 勝ち負け一致 37 - - 必勝ゲーム+必敗ゲーム なら初手で必勝を必敗に変えて常にその状態を保てば勝てる。 38 - ゆえに勝ち負けが一致しないなら和をとったゲームは必勝。 39 - 必敗 + 必敗 = 必敗 40 - 必勝 + 必敗 = 必勝 36 +補題：必敗 + 必敗 = 必敗 37 + - どう動かしてもと必勝+必敗になるので必敗+必敗に戻されて負ける 38 + 39 +補題：必勝 + 必敗 = 必勝 40 + - 必敗+必敗 に動かせばよい 41 + 42 +定理：【等価(和を取ると必敗) => 勝ち負け一致】 43 + - 勝ち負け不一致=>必勝が上の補題で言えているので証明終了 41 44 42 45 注意： 43 46 必勝 + 必勝 = 必敗 44 47 は成り立たない！ *2 + *1 は 初手で *1 + *1 に行けるのでこれは勝てる 45 48 46 49 補題：G+G は必敗 47 50 - まねっこmoveをされると負けるしかない 48 51 49 -補題：A≡B ならば A+C≡B+C 50 - - A+C+B+C = (A+B)+(C+C) = 必敗+必敗 = 必敗 52 +補題：A≡A', B≡B' ならば A+B≡A'+B' 53 + - A+B+A'+B' = (A+A')+(B+B') = 必敗+必敗 = 必敗 51 54 52 -補題：A≡B ならば {A,G1,G2,...}≡{B,G1,G2,...} 53 - - {A,G1,G2,...}+{B,G1,G2,...} は必敗。なぜならこちらがどう動かしても 54 - A+B, G1+G1, G2+G2, ... のいずれかの必敗状態に遷移させられるから。 55 +補題：Ai≡Ai' ならば {A0,A1,A2,...}≡{A0',A1',A2',...} 56 + - {A0,A1,A2,...}+{A0',A1',A2',...} は必敗。なぜならこちらがどう動かしても 57 + A0+A0', A1+A1', A2+A2', ... のいずれかの必敗状態に遷移させられるから。 55 58 56 59 ------------------------------------------------------------------------------------------- 57 60 定理【ゲームの和はxor】 58 61 - *n1 + *n2 = *(n1 xor n2) 59 62 - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 60 63 61 64 証明 62 65 - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 63 66 - (n1 xor n2 xor (n1 xor n2)) は 0 である 64 67 - 一手動かすと 0 じゃなくなる 65 68 >> n1 と n2 と n1^n2 のどれか一個だけビットが変わるので絶対xorが変わるから 66 69 - 相手は一手動かして 0 に戻せる 67 - >> 常に 70 + >> a^b^c = x が非ゼロの場合 a=>a^x か b=>b^x か c=>c^x と動かせばよい 71 + >> つまりa,b,cのどれかは^xすると減ることを言えばよい。 72 + >> a,b,cのうち最上位ビットが立っているものが奇数個ならxも立つのでxorすれば減る 73 + >> 偶数個(2個)なら、その最上位ビットを無視した残りをa',b',c'とするとこれも 74 + >> xorがxなので数学的帰納法的にやることにより巧い減らし方が見つかる。 68 75 - よって最終局面"全部 0"になるのは絶対に自分のターン 69 - 70 76 71 77 ------------------------------------------------------------------------------------------- 72 78 定理【ゲームの状態遷移はmex】 73 79 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 74 80 where mex(S) = min(nat \setminus S) 75 81 76 82 - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) ................................................................................ 90 96 91 97 ・一手動かした次の局面が *n1 または *n2 または ... なゲーム 92 98 {*n1, ..., *nk} = *mex(n1, ..., nk) 93 99 ・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム 94 100 *n1 + *n2 = *(n1 xor n2) 95 101 ・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム 96 102 *n1 <+> *n2 = *(n1 + n2) //単に１個の山なのとかわらない 97 -・両方一手ずつ進めるゲーム？ 103 +・両方一手ずつ進めるゲーム？？？？？ 98 104 *n1 X *n2 = ?