読者です 読者をやめる 読者になる 読者になる

PKU 1082 Calendar Game

問題文: 1082 -- Calendar Game

ゲーム木探索できるようになってうれしい

(その状態から遷移できる中でひとつでも負けの状態(false)があるとreturn trueするやつ使いやすい)

#include <iostream>
#include <cstring>
using namespace std;

int leap(int n){
	return n % 400 == 0 || (n%100 != 0 && n % 4 == 0);
}

static int getDays(int y, int m, int d)
{
  if(m <= 2){
    --y;
    m += 12;
  }
  int dy = 365 * (y - 1);
  int c = y / 100;
  int dl = (y >> 2) - c + (c >> 2);
  int dm = (m * 979 - 1033) >> 5;
  return dy + dl + dm + d - 1;
}

int days(int year,int i){
	if(i==2) return leap(year) ? 29 : 28;
	else if(i==4||i==6||i==9||i==11) return 30;
	else return 31;
}

char memo[2010][13][32];
int f(int y,int m,int d){
	if( getDays(y,m,d) > getDays(2001,11,4) ) return memo[y][m][d] = true;
	if(~memo[y][m][d]) return memo[y][m][d];
	
	// 1日進めるほう
	if(m == 12 && d == days(y,m)){
		if( !f(y+1,1,1) ) return memo[y][m][d] = true;
	}else if(d == days(y,m)){
		if( !f(y,m+1,1) ) return memo[y][m][d] = true;
	}else{
		if( !f(y,m,d+1) ) return memo[y][m][d] = true;
	}
	
	// 1ヶ月進めるほう
	if(m == 12){
		if( !f(y+1,1,d) ) return memo[y][m][d] = true;
	}else{
		if( !f(y,m+1,d) ) return memo[y][m][d] = true;
	}
	
	return memo[y][m][d] = false;
}

int main(){
	int T;cin >> T;
	memset(memo,-1,sizeof(memo));
	while(T--){
		int y,m,d; cin >> y >> m >> d;
		cout << ( f(y,m,d) ? "YES" : "NO" ) << endl; 
	}
}