ADDED   SRM/637-U/1A.cpp
Index: SRM/637-U/1A.cpp
==================================================================
--- SRM/637-U/1A.cpp
+++ SRM/637-U/1A.cpp
@@ -0,0 +1,127 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <tuple>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class GreaterGame { public:
+	double calc(vector <int> hand, vector <int> sothe)
+	{
+		const int N = hand.size();
+
+		set<int> me, you, rest;
+		for(int c=1; c<=2*N; ++c) rest.insert(c);
+		for(int c: hand) me.insert(c), rest.erase(c);
+		for(int c: sothe) you.insert(c), rest.erase(c);
+
+		double ans = 0.0;
+		while(!you.empty() && *you.rbegin()>0)
+		{
+			int y = *you.rbegin(); you.erase(y);
+
+			auto it = me.rbegin();
+			if(*it > y) {
+				while(*it>y) {
+					auto kt = it;
+					++kt;
+					if(kt==me.rend() || *kt<y)
+						break;
+					it = kt;
+				}
+				me.erase(*it);
+				++ans;
+			} else {
+				me.erase(me.begin());
+			}
+		}
+
+		for(int c: me)
+			ans += count_if(rest.begin(), rest.end(), [&](int y){return y<c;}) / (double)rest.size();
+		return ans;
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const double& Expected, const double& Received) {
+ bool ok = (abs(Expected - Received) < 1e-9);
+ if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END	 verify_case(_, GreaterGame().calc(hand, sothe));}
+int main(){
+
+CASE(0)
+	int hand_[] = {4,2};
+	  vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 
+	int sothe_[] = {-1,-1};
+	  vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 
+	double _ = 1.5; 
+END
+CASE(1)
+	int hand_[] = {4,2};
+	  vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 
+	int sothe_[] = {1,3};
+	  vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 
+	double _ = 2.0; 
+END
+CASE(2)
+	int hand_[] = {2};
+	  vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 
+	int sothe_[] = {-1};
+	  vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 
+	double _ = 1.0; 
+END
+CASE(3)
+	int hand_[] = {1,3,5,7};
+	  vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 
+	int sothe_[] = {8,-1,4,-1};
+	  vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 
+	double _ = 2.5; 
+END
+CASE(4)
+	int hand_[] = {6,12,17,14,20,8,16,7,2,15};
+	  vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 
+	int sothe_[] = {-1,-1,4,-1,11,3,13,-1,-1,18};
+	  vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 
+	double _ = 8.0; 
+END
+/*
+CASE(5)
+	int hand_[] = ;
+	  vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 
+	int sothe_[] = ;
+	  vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 
+	double _ = ; 
+END
+CASE(6)
+	int hand_[] = ;
+	  vector <int> hand(hand_, hand_+sizeof(hand_)/sizeof(*hand_)); 
+	int sothe_[] = ;
+	  vector <int> sothe(sothe_, sothe_+sizeof(sothe_)/sizeof(*sothe_)); 
+	double _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/637-U/1B.cpp
Index: SRM/637-U/1B.cpp
==================================================================
--- SRM/637-U/1B.cpp
+++ SRM/637-U/1B.cpp
@@ -0,0 +1,169 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <tuple>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class PathGame { public:
+	string judge(vector <string> board)
+	{
+		vector<int> s;
+		for(int i=0; i<board[0].size(); ++i)
+			s.push_back((board[0][i]=='#')+(board[1][i]=='#')*2);
+		return firstWins(s) ? "Snuke" : "Sothe";
+	}
+
+	bool firstWins(const vector<int>& s)
+	{
+		memo.assign(s.size()*10, -1);
+
+		vector<int> games;
+
+		int i = 0;
+		if(s[0] == 0)
+		{
+			int e = find_if(s.begin()+i, s.end(), [&](int v){return v!=0;}) - s.begin();
+			int L = 0;
+			int N = e-i;
+			int R = e==s.size() ? 0 : s[e];
+			games.push_back(grundy(L,N,R));
+			i = e;
+		}
+		while(i < s.size())
+		{
+			int L = s[i];
+			i = find(s.begin()+i, s.end(), 0) - s.begin();
+			int e = find_if(s.begin()+i, s.end(), [&](int v){return v!=0;}) - s.begin();
+			int N = e-i;
+			int R = e==s.size() ? 0 : s[e];
+			games.push_back(grundy(L,N,R));
+			i = e;
+		}
+
+		return xor_all(games) != 0;
+	}
+
+	vector<int> memo;
+	int grundy(int L, int N, int R)
+	{
+		if(N == 0)
+			return 0; // no move
+		if(N == 1) {
+			if(L==0 || R==0 || L==R)
+				return 1;
+			return 0;
+		}
+
+		int key = N*9+L*3+R;
+		if(memo[key] >= 0)
+			return memo[key];
+
+		vector<int> next;
+		for(int i=0; i<N; ++i)
+		{
+			if(i==0) {
+				if(L!=2) next.push_back(grundy(1,N-1,R));
+				if(L!=1) next.push_back(grundy(2,N-1,R));
+			} else if(i==N-1) {
+				if(R!=2) next.push_back(grundy(L,N-1,1));
+				if(R!=1) next.push_back(grundy(L,N-1,2));
+			} else {
+				next.push_back(grundy(L,i,1)^grundy(1,N-i-1,R));
+				next.push_back(grundy(L,i,2)^grundy(2,N-i-1,R));
+			}
+		}
+		return memo[key] = mex(next);
+	}
+
+	int xor_all(const vector<int>& games)
+	{
+		int v = 0;
+		for(int g: games)
+			v ^= g;
+		return v;
+	}
+
+	int mex(const vector<int>& games)
+	{
+		set<int> gs(games.begin(), games.end());
+		for(int v=0;; ++v)
+			if(gs.count(v)==0)
+				return v;
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const string& Expected, const string& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END	 verify_case(_, PathGame().judge(board));}
+int main(){
+
+CASE(0)
+	string board_[] = {"#.."
+,"..."};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = "Snuke"; 
+END
+CASE(1)
+	string board_[] = {"#"
+,"."};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = "Sothe"; 
+END
+CASE(2)
+	string board_[] = {"....."
+,"..#.."};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = "Sothe"; 
+END
+CASE(3)
+	string board_[] = {".#..."
+,"....."};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = "Snuke"; 
+END
+CASE(4)
+	string board_[] = {".....#..#........##......."
+,"..........#..........#...."};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = "Snuke"; 
+END
+/*
+CASE(5)
+	string board_[] = ;
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = ; 
+END
+CASE(6)
+	string board_[] = ;
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/637-U/1C-U.cpp
Index: SRM/637-U/1C-U.cpp
==================================================================
--- SRM/637-U/1C-U.cpp
+++ SRM/637-U/1C-U.cpp
@@ -0,0 +1,128 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <tuple>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class ConnectingGame { public:
+	string isValid(vector <string> board)
+	{
+		return hasCuttingPaint(board) ? "invalid" : "valid";
+	}
+
+	bool hasCuttingPaint(vector<string> board) {
+		const int H = board.size();
+		const int W = board[0].size();
+		if(H==1 || W==1)
+			return false;
+
+		set<char> T,L,R,B;
+		map<char, set<char>> G;
+
+		for(int y=0; y<H; ++y)
+		for(int x=0; x<W; ++x)
+		{
+			if(y==0) T.insert(board[y][x]);
+			if(y==H-1) B.insert(board[y][x]);
+			if(x==0) L.insert(board[y][x]);
+			if(x==W-1) R.insert(board[y][x]);
+
+			int dy[]={0,0,-1,+1};
+			int dx[]={-1,+1,0,0};
+			for(int d=0; d<4; ++d) {
+				int yy=y+dy[d], xx=x+dx[d];
+				if(0<=yy&&yy<H&&0<=xx&&xx<W&&board[y][x]!=board[yy][xx])
+					G[board[y][x]].insert(board[yy][xx]);
+			}
+		}
+
+		// Is there a way to paint nodes in G s.t.
+		// - all L~G~R paths have at least one Blue node, and
+		// - all T~G~B paths have at least one Red node?
+		// |G|<=62.
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const string& Expected, const string& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END	 verify_case(_, ConnectingGame().isValid(board));}
+int main(){
+
+CASE(0)
+	string board_[] = {"AAB"
+,"CCD"};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = "invalid"; 
+END
+CASE(1)
+	string board_[] = {"AA"
+,"BB"};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = "valid"; 
+END
+CASE(2)
+	string board_[] = {"iii"
+,"iwi"
+,"iii"};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = "valid"; 
+END
+CASE(3)
+	string board_[] = {"SSnukee"
+,"SKnuthe"
+,"SSSothe"};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = "invalid"; 
+END
+CASE(4)
+	string board_[] = {"rng58"
+,"rnggn"
+,"rnnnn"};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = "valid"; 
+END
+CASE(5)
+	string board_[] = {"ggssGGGGGG","ggssspGGGG","ggsssppGGG","ggWsspGGGG","gggsspGGiG","g7ssspGGGG","gggsseKK33","gggssssK33","gHgsssHA33","HHHHHHHHHH","HHHHHHHHH6","HHHHHHHHb6"};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = "invalid"; 
+END
+/*
+CASE(6)
+	string board_[] = ;
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = ; 
+END
+CASE(7)
+	string board_[] = ;
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	string _ = ; 
+END
+*/
+}
+// END CUT HERE

Index: lib/doc/nim.txt
==================================================================
--- lib/doc/nim.txt
+++ lib/doc/nim.txt
@@ -8,11 +8,11 @@
   - 無限ループしない
 
 nim
   - n 個の石の山がある
   - 一手で 1 ～ n 個取っていい
-  - 最後の石を取った方が勝ち（石がなくなって打つ手が無くなった方が負け）
+  - 石がなくなって打つ手が無くなった方が負け（最後の石を取った方が勝ち）
 
 *n をサイズ n の山が1個だけの nim とする
   - *0 は負け
   - *n は勝ち n>=1
 
@@ -25,35 +25,38 @@
   - G1 + G2 を、G1 と G2 の二つのゲームがあって、どちらかを選んで一手進められるゲームとする。
     すなわち G1 + G2 = {(v,G2) | v∈G1} ∪ {(G1,u) | u∈G2} 
 
 等価
   - 二つのゲームG, Fが等価なことを G ≡ F と書く
-    等価というのは勝ち負け一致よりもっと強い。二つのゲームの和 G+F が必敗になること。
+    等価というのは勝ち負け一致よりもっと強い。二つのゲームの和 G+F が必敗になることと定義する。
     たとえば *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない
     等価というのは可能な動きの構造がisomorphic/bisimilarというよりは弱い。
     たとえば以下で示すように *1 + *3 ≡ *2 だが初手のパターン数など違う。
 
 -------------------------------------------------------------------------------------------
-定理：等価(和を取ると必敗) => 勝ち負け一致
-  - 必勝ゲーム+必敗ゲーム なら初手で必勝を必敗に変えて常にその状態を保てば勝てる。
-    ゆえに勝ち負けが一致しないなら和をとったゲームは必勝。
-      必敗 + 必敗 = 必敗
-      必勝 + 必敗 = 必勝
+補題：必敗 + 必敗 = 必敗
+　- どう動かしてもと必勝+必敗になるので必敗+必敗に戻されて負ける
+
+補題：必勝 + 必敗 = 必勝
+　- 必敗+必敗 に動かせばよい
+
+定理：【等価(和を取ると必敗) => 勝ち負け一致】
+  - 勝ち負け不一致=>必勝が上の補題で言えているので証明終了
 
     注意：
       必勝 + 必勝 = 必敗
     は成り立たない！ *2 + *1 は 初手で *1 + *1 に行けるのでこれは勝てる
 
 補題：G+G は必敗
 　- まねっこmoveをされると負けるしかない
 
-補題：A≡B ならば A+C≡B+C
-  - A+C+B+C = (A+B)+(C+C) = 必敗+必敗 = 必敗
+補題：A≡A', B≡B' ならば A+B≡A'+B'
+  - A+B+A'+B' = (A+A')+(B+B') = 必敗+必敗 = 必敗
 
-補題：A≡B ならば {A,G1,G2,...}≡{B,G1,G2,...}
-　- {A,G1,G2,...}+{B,G1,G2,...} は必敗。なぜならこちらがどう動かしても
-    A+B, G1+G1, G2+G2, ... のいずれかの必敗状態に遷移させられるから。
+補題：Ai≡Ai' ならば {A0,A1,A2,...}≡{A0',A1',A2',...}
+　- {A0,A1,A2,...}+{A0',A1',A2',...} は必敗。なぜならこちらがどう動かしても
+    A0+A0', A1+A1', A2+A2', ... のいずれかの必敗状態に遷移させられるから。
 
 -------------------------------------------------------------------------------------------
 定理【ゲームの和はxor】
   - *n1 + *n2 = *(n1 xor n2)
   - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2)
@@ -62,13 +65,16 @@
     - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。
     - (n1 xor n2 xor (n1 xor n2)) は 0 である
     - 一手動かすと 0 じゃなくなる
         >> n1 と n2 と n1^n2 のどれか一個だけビットが変わるので絶対xorが変わるから
     - 相手は一手動かして 0 に戻せる
-        >> 常に 
+        >> a^b^c = x が非ゼロの場合 a=>a^x か b=>b^x か c=>c^x と動かせばよい
+        >> つまりa,b,cのどれかは^xすると減ることを言えばよい。
+        >> a,b,cのうち最上位ビットが立っているものが奇数個ならxも立つのでxorすれば減る
+        >> 偶数個(2個)なら、その最上位ビットを無視した残りをa',b',c'とするとこれも
+        >> xorがxなので数学的帰納法的にやることにより巧い減らし方が見つかる。
     - よって最終局面"全部 0"になるのは絶対に自分のターン
-
 
 -------------------------------------------------------------------------------------------
 定理【ゲームの状態遷移はmex】
   - {*n1, ..., *nk} ≡ *mex(n1,...,nk)
       where mex(S) = min(nat \setminus S)
@@ -92,7 +98,7 @@
 　　{*n1, ..., *nk} = *mex(n1, ..., nk)
 ・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム
 　　*n1 + *n2 = *(n1 xor n2)
 ・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム
 　　*n1 <+> *n2 = *(n1 + n2)     //単に１個の山なのとかわらない
-・両方一手ずつ進めるゲーム？
+・両方一手ずつ進めるゲーム？？？？？
 　　*n1 X *n2 = ?