POJ 2311 - Cutting Game

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

概要

W * H のグリッドからなる紙を，2人のプレイヤーが順にグリッドに沿って水平方向か垂直方向に切っていく． N ターン後は N+1 枚の紙が存在しており，プレイヤーはどの紙を切ってもよい．

もしプレイヤーが切って 1 * 1 の紙を作り出すことができたら，そのプレイヤーの勝利である．

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

制約

• 2 <= W, H <= 200

解法

grundy number で解く．

2 * 2, 3 * 2, 2 * 3 の紙しか残っていないときに負けが決定するので，これらが terminal position であり grundy number は 0 である．

w * h の紙のとき，垂直方向に k の位置で切ると (w-k) * h と k * h の2つの部分ゲームに分かれるので，この2つの状態の grundy number の xor が w * h から遷移できる grundy number となる． 水平方向も同様．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 static const int N = 200;
 6 int memo[N+1][N+1];
 7 
 8 int grundyNumber(int w, int h)
 9 {
10   if (memo[w][h] != -1) {
11     return memo[w][h];
12   }
13   bool s[N+1];
14   fill_n(s, N+1, false);
15   for (int k = 2; w-k >= 2; k++) {
16     s[grundyNumber(w-k, h) ^ grundyNumber(k, h)] = true;
17   }
18   for (int k = 2; h-k >= 2; k++) {
19     s[grundyNumber(w, h-k) ^ grundyNumber(w, k)] = true;
20   }
21   int n = 0;
22   for (; s[n]; n++);
23   return memo[w][h] = n;
24 }
25 
26 int main()
27 {
28   for (int i = 0; i <= N; i++) {
29     fill_n(memo[i], N+1, -1);
30   }
31   memo[2][2] = 0;
32   memo[3][2] = memo[2][3] = 0;
33   int W, H;
34   while (scanf("%d %d", &W, &H) != EOF) {
35     puts(grundyNumber(W, H) == 0 ? "LOSE" : "WIN");
36   }
37   return 0;
38 }