Algoogle

Algorithm for Programming Contest

AOJ 1230 Nim

Category: AOJ Tag: dp

Nim

問題概要


解法


i : プレイヤー番号(0〜2n)
j : 残りの石の数
dp[i][j] := 必勝法が存在するか否か

j = 1 のときは当然その一個を取らなければいけないので必ず負けるので
dp[i][1] = 0
あとは j が少ない順にループを回して
dp[i+1][j-k] (1 <= k <= m[i])
に負ける場合が含まれる場合は
dp[i][j] = 1 それ以外の場合は
dp[i][j] = 0

この調べ方なら自分は次の相手に対する勝ち負けを判定していき, それが一周回っていくので
0番のプレイヤーの勝敗がそのチームの勝敗になる.
答えはdp[0][s]

コード


(1230.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
#include <cstdio>

#define rep(i,a) for(int i = 0;i < (a); i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)

using namespace std;

int n, S;
int M[21];

int main(){
    while(scanf("%d", &n), n){
        scanf("%d", &S);
        rep(i,2*n) scanf("%d", M+i);
        int dp[21][(1<<13)+1] = {-1};
        repi(j, 1, S+1)
            rep(i, 2*n)
                if(j == 1) dp[i][j] = 0;
                else{
                    repi(k, 1, M[i]+1)
                        if(j - k < 1) break;
                        else if(dp[(i+1)%(2*n)][j-k] == 0)
                            dp[i][j] = 1;
                    if(dp[i][j] == -1) dp[i][j] = 0;
                }
        printf("%d\n", dp[0][S]);
    }
    return 0;
}

Comments