SRM574 Div1 Easy "TheNumberGame"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12474
訳
マナ男は最近Number Gameと呼んでいるゲームを考え出した。
彼はそのゲームで友達と対戦する。
まず始めにマナ男はAという数字を、友達はBという数字を与えられる。
A, Bのどちらにも0は含まれていない。
最初はマナオのターンであり、マナオと友達で交互にターンが回ってくる。
各ターンでプレイヤーは自分の数字を、リバースするか10で割る、
のどちらかの操作を選ぶ事ができる。
例えば12849という数字を持っていたとしたら、
リバースして94821とするか、10で割って1284とする、のどちらかを行う。
相手の数字を操作する事は出来ない。
もし、各ターンでA,Bの数字が等しくなったら、マナオの勝ちとする。
ただし、1000ターン(マナオ500ターン、友達500ターン)かかっても、
同じに出来なかった場合はマナオの負けとなる。
数字A, Bが与えられるので、マナオが勝つか負けるかを返せ。
制約
1 <= A,B <= 999,999,999
A != B
考えた事
与えられる数字の桁数が9桁と少ないので、
A, Bを文字列とみなして、
AにBが部分文字列として含まれていれば、
必ず1000ターン以内に追い詰める事ができる。
AにBが部分文字列として含まれていなければ、
Bはリバースばっかりやってれば1000ターン超過させる事ができる。
クソゲーである。
事後
ターン数を指定された時どうやってこの問題とくのかなと思ったので、
dfsで実装練習。
マナオのターンの場合、
リバースした時と割った時、
どちらかの行動で勝てればマナオは勝つことができる。
友達のターンの場合、
リバースした時と割った時、
どちらの行動をとっても負けるときのみ、マナオは勝つことができる。
Aの桁数をa、Bの桁数をb、最長ターンをnとする。
メモ化再帰でやると計算量はO(a^2 * b^2 * n)
ソースコード
int memo[9][9][9][9][1001]; int N = 1000; // 規定ターン数 class TheNumberGame { public: string A, B; // AとBは同じになってるか? bool same( int as, int ae, int bs, int be ){ if( abs( as - ae ) != abs( bs - be ) ) return false; int n = abs( as - ae ); int da = as < ae ? 1 : -1; int db = bs < be ? 1 : -1; for( int a = as, b = bs, i = 0; i <= n; a += da, b += db, i++ ){ if( A[a] != B[b] ) return false; } return true; } // 10で割るとどんなインデックスになる? void cut( int s, int e, int* cs, int* ce ){ *cs = s; *ce = s < e ? e - 1 : e + 1; } // A(index as - ae) B(index bs - be) 経過ターンn の時 // マナオは勝てるか? bool dfs( int as, int ae, int bs, int be, int n ){ // ターン超過 if( n > N ) return false; int& m = memo[as][ae][bs][be][n]; // memoってたらそれを返す if( m != -1 ){ return m == 1; } // 同じになってたら勝ち if( same( as, ae, bs, be ) ){ m = 1; return true; } bool win; // マナオのターン if( n % 2 == 0 ){ win = false; // 割る if( as != ae ){ int cs, ce; cut( as, ae, &cs, &ce ); win |= dfs( cs, ce, bs, be, n+1 ); } // リバース win |= dfs( ae, as, bs, be, n+1 ); } // 友達のターン else{ win = true; // 割る if( bs != be ){ int cs, ce; cut( bs, be, &cs, &ce ); win &= dfs( as, ae, cs, ce, n+1 ); } // リバース win &= dfs( as, ae, be, bs, n+1 ); } // メモして返す m = win ? 1 : 0; return win; } string determineOutcome(int _A, int _B){ ostringstream oss1; oss1 << _A; A = oss1.str(); ostringstream oss2; oss2 << _B; B = oss2.str(); for( int i = 0; i < 9; i++ ) for( int j = 0; j < 9; j++ ) for( int k = 0; k < 9; k++ ) for( int l = 0; l < 9; l++ ) for( int n = 0; n < 1000; n++ ){ memo[i][j][k][l][n] = -1; } N = 1000; bool ok = dfs( 0, A.length()-1, 0, B.length()-1, 0 ); return ok ? "Manao wins" : "Manao loses"; } };