SRM619 div1easy SplitStoneGame

考えたこと

ゲームで石の山だしgrundy数かなあと思いつつ問題文を読む。敗北条件を考えると石の数が1個以下の山しか存在しない場合か山が2個以下しかない場合になる。サンプルを読んでいると山の石の数は2個以上か1個の2パターンしか考慮しなくていいことに気づく。1個の山の数をA、2個以上の山の数をBと置く。
それぞれの手番でのA, Bの遷移がどうなってるか考えると
* Bがマイナス1 (B>=3)
* Aがマイナス1 (A>=1, B>=2)
* Bがプラス1、Aがマイナス2 (A>=2, B>=1)
の3通りになる。
AとBからwinとloseの状態を一意に決めることができ、メモ化再帰で求めることでできる。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

int dp[55][55];

int dfs(int A, int B) {
  if(dp[A][B] != -1) return dp[A][B];
  if(A+B <= 2 || B == 0)  return dp[A][B] = 0;

  bool res = true;
  if(B >= 3) res &= dfs(A, B-1);
  if(A >= 1 && B >= 2) res &= dfs(A-1, B);
  if(A >= 2 && B >= 1) res &= dfs(A-2, B+1);
  return dp[A][B] = !res;
}

class SplitStoneGame {
   public:
   string winOrLose(vector <int> number)
  {
    int a = 0, b = 0;
    REP(i, number.size()) {
      if(number[i] == 1) a++;
      else b++;
    }
    memset(dp, -1, sizeof(dp));
    if(dfs(a, b) == 0) return "LOSE";
    return "WIN";
  }
};