POJ-1082, LiveArchive-2321, TJU-1468, ZOJ-1024 : Calendar Game

問題概要

カレンダーを1日進めるか1ヶ月進めるか選ぶことができる。ふたりで交互に手を選んだとき、自分の番で特定の日付に遷移できるかどうか判定する問題。

解法

基本的には典型的なゲーム木探索。日付の存在判定なんかは適当に頑張る。サイズが小さいので相当愚直にやっても大丈夫そう。

acceptされたコード

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_D = 365 * 105;

const int ds[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool is_leap_year(int year){
	return year % 400 == 0 || (year % 100 != 0 && year % 4 == 0);
}

struct day{
	int y, m, d;
	day(){}
	day(int y, int m, int d):y(y), m(m), d(d){}
};

bool operator<(const day& lhs, const day& rhs){
	return lhs.y != rhs.y ? lhs.y < rhs.y :
			lhs.m != rhs.m ? lhs.m < rhs.m :
					lhs.d < rhs.d;
}

int D;
day days[MAX_D];
bool win[MAX_D];

void touch(){
	for(int y=1900; y<=2002; y++){
		for(int m=0; m<12; m++){
			for(int d=0, ed=ds[m] + ((m==1 && is_leap_year(y)) ? 1 : 0); d<ed; d++){
				days[D++] = day(y, m, d);
			}
		}
	}
}

void solve(){
	memset(win, true, sizeof(win));
	int start = lower_bound(days, days+D, day(2001, 10, 3)) - days;
	win[start] = false;
	for(int i=start-1; i>=0; i--){
		win[i] = false;
		if(!win[i + 1]){
			win[i] = true;
			continue;
		}
		else{
			day nxt = days[i];
			nxt.m++;
			if(nxt.m == 12){
				nxt.y++;
				nxt.m = 0;
			}
			if(binary_search(days, days+D, nxt) && !win[lower_bound(days, days + D, nxt) - days]){
				win[i] = true;
			}
		}
	}
}

int main(){
	touch();
	solve();
	int T;
	scanf("%d", &T);
	for(;T--;){
		int y, m, d;
		scanf("%d%d%d", &y, &m, &d);
		m--; d--;
		puts(win[lower_bound(days, days+D, day(y,m,d)) - days] ? "YES" : "NO");
	}

	return 0;
}