WARush

SRMの結果とか、解けた問題のコードを書いていきます

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";
    }
};