LiveArchive6470 Chomp

問題概要
３×３のチョコがある。左下端のチョコは毒である。２人でプレイして交互に食べていく。選んだ位置を含めて右上は除去される。左下端を選ばざる得なくなった時点で負けである。初めの状態が与えられるので、最善の手を尽くすとき、はじめはどこを食べれば勝つことが出来るかを出力せよ。

解法
あらゆる位置の選択に対して、右上が削れるように３行のそれぞれの要素を減らしながらメモ化再帰する。

#include <bits/stdc++.h>

using namespace std;

int const MAX_N = 110;

// [TopSize][MiddleSize][BottomSize]
int memo[MAX_N][MAX_N][MAX_N];
int X[MAX_N][MAX_N][MAX_N];
int Y[MAX_N][MAX_N][MAX_N];

//  y
//  ^
// -|--> x

#define TOP 2
#define MIDDLE 1
#define BOTTOM 0

#define WIN 1
#define LOSE 0
#define NORECORD -1

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

int rec(int top, int middle, int bottom) {
  int &ret = memo[top][middle][bottom];
  if(ret != NORECORD) return ret;
  
  rep(pos, top) if(!rec(pos, middle, bottom)) {
    X[top][middle][bottom] = pos;
    Y[top][middle][bottom] = TOP;
    return ret = WIN;
  }
  
  rep(pos, middle) if(!rec(min(pos, top), pos, bottom)) {
    X[top][middle][bottom] = pos;
    Y[top][middle][bottom] = MIDDLE;
    return ret = WIN;
  }
  
  REP(pos, 1, bottom) if(!rec(min(pos, top), min(pos, middle), pos)) {
    X[top][middle][bottom] = pos;
    Y[top][middle][bottom] = BOTTOM;
    return ret = WIN;
  }
  
  return ret = LOSE;
}

int main() {
  
  fill(memo[0][0], memo[0][0]+MAX_N*MAX_N*MAX_N, NORECORD);
  
  int Tc; cin >> Tc;
  while(Tc--) {
    int Tcnt; cin >> Tcnt;
    int top, middle, bottom;
    cin >> bottom >> middle >> top;
    
    if(rec(top, middle, bottom)) {
      cout << Tcnt << " W " << X[top][middle][bottom]+1 << " " << Y[top][middle][bottom]+1 << endl;
    }
    else {
      cout << Tcnt << " L\n";
    }
  }
  
  return 0;
}

メモ
二人の勝ち負けが交互に決まるゲーム理論→戻り値が二値のメモ化再帰で解け、みたいなのがある。何を状態として持ち、何をメモするか、を考えてやる。この場合勝ち負けがメモの内容になりそう。この問題はプレイヤーによって行う処理は変わらない。まず全パターンの取り除く処理をつくろう。サンプルでは[2,2]を取り除いたところから始まっている。選ぶとその右側が消えて、その上部も消えると見ることが出来る。１行目だったら上部はないので消えない、２行目だったら１行目が消える。３行目だったら上部１，２行が消える。各行の左から見たサイズを状態として再帰すればよい。各行のサイズを状態とするのは入力が p, q, r であるから妥当だ。