Algoogle

Algorithm for Programming Contest

LiveArchive 5760 Alice and Bob

Category: LiveArchive Tag: dp

Alice and Bob

問題概要


N個の山にそれぞれAi個石が置いてある.
AliceとBobはAliceから交互に以下の操作のどちらかを行う.

  • 1つの山から1つ石を取る
  • 2つの山をマージする

先に操作が出来なくなった方の負け.
N <= 50
Ai <= 1000
テストケース <= 4000

解法


操作に制限を加えて考えてメモ化再帰します.
dp[i][j] := 残り1つの山がi個, それ以外の山の石の和とその山の数-1の和がjのときの勝敗
こうするとマージに関して, 残り1つでない山のマージは石を1つ取り除くことに対応する.
あとは全パターンメモ化再帰で試す.
次が負け状態のやつに移動できる場合は勝ち. それ以外は負け.
毎ステップとれる行動は

  • 石が1つだけの山から取る
  • 石が2つ以上ある山から取る
  • 石が1つだけの山と2つ以上の山をマージする
  • 石が1つだけの山同士でマージする

またそのメモは使いまわせるのでテストケースごとに初期化しないようにする(初期化すると間に合わない)

コード


(5760.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int N, A;
int dp[64][65536];

bool rec(int i,int j){
    if(dp[i][j] >= 0) return dp[i][j];
    if(j == 1) return dp[i][j] = rec(i+1,0);
    dp[i][j] = 0;
    if(i) dp[i][j] |= !rec(i-1,j);
    if(j) dp[i][j] |= !rec(i,j-1);
    if(i && j) dp[i][j] |= !rec(i-1,j+1);
    if(i >= 2) dp[i][j] |= !rec(i-2,j+2+(j>0));
    return dp[i][j];
}

int main(){
    int T;
    memset(dp,-1,sizeof(dp));
    scanf("%d", &T);
    for(int i = 1; i <= T; i++){
        scanf("%d",&N);
        int a = 0, b = 0;
        for(int i = 0; i < N; i++){
            scanf("%d", &A);
            if(A == 1) a++;
            else b += A + 1;
        }
        printf("Case #%d: ", i);
        if(rec(a,max(0,b-1))) printf("Alice\n");
        else printf("Bob\n");
    }
    return 0;
}

Comments