Codeforces Round #173 Yet Another Number Game

問題概要

n個の非負整数が与えられる（1 <= n <= 3）。この非負整数を使って２人がゲームをする。それぞれのプレイヤーは自分の手番にて以下のいずれかの処理を行う。

1. n個の非負整数から任意の正数を選ぶ（これをxとおく）。その正数から1以上x以下の正数を引く。
2. n個の非負正数から最小のものを選ぶ（これをxとおく）。すべての非負正数から1以上x以下の正数を引く。

これを交互に繰り返し、いずれの操作も行えなくなった方が負け。お互い最善手を指したときどちらが勝つか答えよ。

解法

最初、動的計画法でといたけど間に合わなかった。以下のように場合分けするとうまくいく。

■n=1のとき
これは自明。非負整数が0であれば先手の負け。そうでなければ先手の勝ち。

■n = 2のとき
これは動的計画法で解ける。

■n = 3のとき
Nimと同様になる。

もうちょっと掘り下げて考えてみる。n=2のときなぜNimと同じにならないか？これはNimにおける負けポジションから負けポジションへ遷移することができるから。例えば、(2, 2)という負けポジションで回ってきても処理2を使って(1, 1)や(0, 0)という負けポジションで相手に返すことができる。

じゃあn=3のときはなぜNimでうまくいくか？
まずNimにおける勝ちポジションからは、処理1を使って負けポジションへ遷移することができる。
よって、Nimにおける負けポジションからは、処理2を使っても負けポジションに遷移させることはできないことを示せばいい。

処理2で引く数をxとおく。このときxを二進数で表したとき1番左にある1のビットを考える。このビットをbビットと呼ぶことにする。
今ゲームで使用している3つの非負整数x, y, zのbビット目のパターンは、負けポジションなので、(0, 0, 0)か(0, 1, 1)である。

■(0, 0, 0)のとき
(0, 0, 0) → (1, 1, 1)となるので、x ^ y ^ z = 0とはならない。

■(0, 1, 1)のとき
(0, 1, 1) → (1, 0, 0)となるので、x ^ y ^ z = 0とはならない。

よって、n = 3のときは処理2を使ってもNimの負けポジションから負けポジションに遷移することはない。したがってn = 3のときはNimと同様に考えることができる。

ソースコード

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)

bool dp[300][300];

void init() {
    REP (i, 300) REP (j, 300) {
        dp[i][j] = false;
        REP (k, i) if (!dp[k][j]) dp[i][j] = true;
        REP (k, j) if (!dp[i][k]) dp[i][j] = true;
        int x = min(i, j);
        FOR (k, 1, x+1) if (!dp[i-k][j-k]) dp[i][j] = true;
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    REP (i, n)
        cin >> a[i];
    init();
    if (n == 1) {
        if (a[0])
            puts("BitLGM");
        else
            puts("BitAryo");
    }
    else if (n == 2) {
        if (dp[a[0]][a[1]])
            puts("BitLGM");
        else
            puts("BitAryo");
    }
    else {
        if (a[0] ^ a[1] ^ a[2])
            puts("BitLGM");
        else
            puts("BitAryo");
    }
    return 0;
}