WARush

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

Codeforces #173 Div2 D "Yet Another Number Game"

問題

奇妙なゲームがある。
ゲームを始めるにあたって、
まず負ではないN個の整数a1, a2 ... aNが与えられる。
そして、以下の2つの操作のどちらかを行う

  • 操作A. a1からaNまでの整数を選び(aiとする)、数値x(1 <= x <= ai)を決め、
それをaiから引く。 ai = ai - x
  • 操作B. a1,a2...aNでの最も小さい数をaiとしたとき、数値x(1 <= x <= ai)を決め、
それをa1,a2...aNで、それぞれxを引く。 a1 = a1 - x, a2 = a2 - x... aN = aN - x

上記の2つの操作のどちらも出来なくなってしまった方の負けである。

ここで、Nと整数a1, a2 ... aNが与えられた時、
先攻後攻どちらが勝つかを出力せよ。

制約

1 <= N <= 3
0 <= ai <= 300

ACしてるコードをカンニング

Nによって場合わけを行う。

N == 1の場合
唯一の整数a1が0なら後攻が勝ち。
それ以外なら先攻が勝ち。


N == 2の場合
Nimのように出来ないか考えてみる。
Nimは次のような考え方から答えを導き出せる

a bを石の数として、
a^b=0の状態で石を取ると、必ずa^b!=0になる。
a^b!=0の状態からa^b=0となる石の取り方が必ず存在する。
a=0, b=0はa^b=0なので、
a^b!=0の状態を迎えたほうが勝ち。

今回のゲームでは、a1 = a2のとき、a1^a2=0で、
Nimにおいては負けなのだが、
操作Bを使うと勝ててしまうので、Nimの考え方は使えない。

そこで、
bool (i, j): a1 = i, a2 = jの時、先攻が勝つか?
のDPを行う。
まず(0,0):= falseとする。
それから各i, jにおいて、
・iをx(1~i)引いてみる
・jをx(1~j)引いてみる
・iとjをx(1~min(i,j))引いてみる
の3つの操作を一通り行った時、
falseとなっているものがあれば、
(i,j) = trueとなる。

計算量はだいたい
300 * 300 * (300 + 300 + 300)/ 2くらい


N == 3の場合
またまたNimのように出来ないか考えてみる。
操作Bを実行して、
a^b=0 から a^b=0に遷移するものが存在しないか考えてみる。

例)
a1 = 5 a2 = 3 a3 = 6
ビット列 1 2 3
         1 0 1 = 5
         0 1 1 = 3
         1 1 0 = 6
  xor  0 0 0 = 0

1を引いてみる
ビット列 1 2 3
         1 0 0 = 4
         0 1 0 = 2
         1 0 1 = 5
  xor  0 1 1 != 0

2を引いてみる
ビット列 1 2 3
         0 1 1 = 3
         0 0 1 = 1
         1 0 0 = 4
  xor  1 1 0 != 0

3を引いてみる
ビット列 1 2 3
         0 1 0 = 2
         0 0 0 = 0
         0 1 1 = 3
  xor  0 0 1 != 0

どうやら3個の時は大丈夫っぽい・・
(証明がよく分からん)

よって、Nimのように、a1^a2^a3が0か否かで判断する。


自分が勘違いしてた部分なのだけど、
n == 3の時、0 3 3のように何か1つでも0になったら、
操作Bは使えない(1 <= x <= 0のようなxはない)んだね・・・

ソースコード
    int n, a[4];
    cin >> n;
    for( int i = 1; i <= n; i++ ){
        cin >> a[i];
    }

    // n == 2用のdp
    bool win[301][301];
    memset( win, false, sizeof(win) );
    for( int i = 0; i <= 300; i++ ){
        for( int j = 0; j <= 300; j++ ){
            bool ok = false;
            // iを1つずつ減らしたのを見ていく
            for( int t = i - 1; t >= 0; t-- ){
                if( !win[t][j] ) ok = true;
            }
            // jを1つずつ減らしたのを見ていく
            for( int t = j - 1; t >= 0; t-- ){
                if( !win[i][t] ) ok = true;
            }
            // 両方減らしたのを見ていく
            for( int t = min(i,j); t >= 1; t-- ){
                if( !win[i-t][j-t] ) ok = true;
            }
            if( ok ) win[i][j] = true;
        }
    }

    if( n == 1 ){
        if( a[1] != 0 ){
            cout <<  "BitLGM" << endl;
        }else{
            cout <<  "BitAryo" << endl;
        }
    }

    if( n == 2 ){
        if( win[a[1]][a[2]] ){
            cout <<  "BitLGM" << endl;
        }else{
            cout <<  "BitAryo" << endl;
        }
    }

    if( n == 3 ){
        int x = a[1] ^ a[2] ^ a[3];
        if( x != 0 ){
            cout <<  "BitLGM" << endl;
        }else{
            cout <<  "BitAryo" << endl;
        }
    }
}