yukicoder No.102 トランプを奪え

問題
2人でゲームをする。まず、一組トランプの中から何枚かをマークごとに分けて重ね山札にして置く。
2人交互に以下の操作を繰り返す。
・4つ(♡♧♤♢)の山札から1つの山札を選びそこから1〜3枚カード引き手札に加える。
・カード引いた時、そのマークの山札がなくなったら相手の手札の半分を自分の手札にすることができる。
・パスはできず必ず1枚は引かなければならない。
全ての山札がなくなったら終了。最終的に手札が多い方の勝ち。
両方が常に最善手を取った場合勝つのは先攻(Taro)か後攻(Jiro)か求める。

感想
山札がなくなった時相手の手札を半分奪えるので、最後の一枚を取った方が勝つ。
それぞれの山札の枚数でメモ化。

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <cstring>
#include <climits>
#include <queue>
#include <utility>
#define INF INT_MAX / 2
using namespace std;

typedef pair<int, int> P;
typedef long long ll;
int memo[2][14][14][14][14];

bool dfs(int t,int n1,int n2,int n3,int n4){
	if(memo[t%2][n1][n2][n3][n4] != 0){
		if(memo[t%2][n1][n2][n3][n4] == 1)return true;
		else return false;
	}
	if(n1+n2+n3+n4==0)return t%2==0?false:true;
	bool ret;

	if(t%2==0){
		ret = false;
		for(int i=1;i<=3;i++){
			if(n1-i>=0)ret |= dfs(t+1,n1-i,n2,n3,n4);
			if(n2-i>=0)ret |= dfs(t+1,n1,n2-i,n3,n4);
			if(n3-i>=0)ret |= dfs(t+1,n1,n2,n3-i,n4);
			if(n4-i>=0)ret |= dfs(t+1,n1,n2,n3,n4-i);
		}
	}	
	else{
		ret = true;
		for(int i=1;i<=3;i++){
			if(n1-i>=0)ret &= dfs(t+1,n1-i,n2,n3,n4);
			if(n2-i>=0)ret &= dfs(t+1,n1,n2-i,n3,n4);
			if(n3-i>=0)ret &= dfs(t+1,n1,n2,n3-i,n4);
			if(n4-i>=0)ret &= dfs(t+1,n1,n2,n3,n4-i);
		}
	}
	if(ret)memo[t%2][n1][n2][n3][n4] = 1;
	else memo[t%2][n1][n2][n3][n4] = -1;
	return ret;
}

int main(void) {
	int n1,n2,n3,n4;
	cin >> n1 >> n2 >> n3 >> n4;

	if(dfs(0,n1,n2,n3,n4))cout << "Taro" << endl;
	else cout << "Jiro" << endl;
}

yukicoderの☆3解いていて心地良い問題が多くて好き。