POJ 2425 - A Chess Game

http://poj.org/problem?id=2425

概要

N 個のノードからなる閉路のない有向なグラフが与えられる． このうち M 個のノード a[1], ..., a[M] に駒が置かれている．

2人のプレイヤーは交互に，1つの駒をそのノードから出ているエッジに沿って1つ進めることができる． そして，どの駒も動かせないときそのプレイヤーは負けとなる．

両プレイヤーが最適な手を選択したとき，先手が勝つか負けるかを答える．

制約

• 1 <= N <= 1000
• 1 <= M <= 10

解法

grundy number で解く．

ちょうど http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames の後半の例とほぼ同じように解ける．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int memo[1000];
 7 int grundyNumber(const vector<vector<int> >& g, int x)
 8 {
 9   int& n = memo[x];
10   if (n != -1) {
11     return n;
12   }
13   bool s[1000];
14   fill_n(s, 1000, false);
15   for (vector<int>::const_iterator it = g[x].begin(); it != g[x].end(); ++it) {
16     s[grundyNumber(g, *it)] = true;
17   }
18   for (n = 0; s[n]; ++n);
19   return n;
20 }
21 
22 int main()
23 {
24   int N;
25   while (scanf("%d", &N) != EOF && N != 0) {
26     vector<vector<int> > g(N);
27     for (int i = 0; i < N; i++) {
28       int X;
29       scanf("%d", &X);
30       for (int j = 0; j < X; j++) {
31         int v;
32         scanf("%d", &v);
33         g[i].push_back(v);
34       }
35     }
36 
37     fill_n(memo, 1000, -1);
38     int M;
39     while (scanf("%d", &M) != EOF && M != 0) {
40       int s = 0;
41       while (M-- > 0) {
42         int x;
43         scanf("%d", &x);
44         s ^= grundyNumber(g, x);
45       }
46       puts(s == 0 ? "LOSE" : "WIN");
47     }
48   }
49   return 0;
50 }