1082 Calendar Game

問題概要

スタートの日付から二人のプレイヤーが交互に日付を動かす。
日付は、カレンダーの次の日または、次の月の同じ日にのみ動かすことができる。
次の月に同じ日がない場合は、そこに動かすことはできない。

2001年11月4日に日付を到着させたほうが勝ちのとき、両者が最善の戦略を取ったとして、先手が勝てるかどうかを判定せよ。
開始の日付は1900年1月1日以降である。また、2001年11月4日を超えて日付を移動させた場合には負けになる。

解法

ゴールの日付から逆向きにDPする。
dp[日付]が、その日付で先手番が始まったときに先手が勝てるかとすると、
次の月と次の日のどちらかで、先手が負け（すなわち、自分が勝つ）ならばdp[日付]は1となる。

最初に勝ち負けを全て計算しておくとよい。
閏年や、月の日数がややこしいので注意する。

ソースコード

すんごく見づらい。

int day[]={31,28,31,30,31,30,31,31,30,31,30,31};
bool g[111][12][31];

bool leap(int y,int m){
	return m==1&&y>0&&y%4==0;
}
int main()
{
	for(int y=101;y<103;y++)for(int m=y==101?10:0;m<12;m++)
	for(int d=y==101&&m==10?4:0;d<day[m];d++)g[y][m][d]=1;
	
	g[101][10][3]=0;
	for(int y=101;y>=0;y--)for(int m=y==101?10:11;m>=0;m--)
	for(int d=y==101&&m==10?2:day[m]+leap(y,m)-1;d>=0;d--)
	{
		int yy=y,mm=m,dd=d+1;
		bool nd,nm;
		if(dd>=day[mm]+leap(yy,mm)){
			dd=0;
			if(++mm>=12)mm=0,yy++;
		}
		nd=g[yy][mm][dd];
		
		yy=y; mm=m+1; dd=d;
		if(mm>=12)yy++,mm=0;
		if(day[mm]+leap(yy,mm)<=dd)nm=1;
		else nm=g[yy][mm][dd];
		
		g[y][m][d]=!nd||!nm;
	}
	
	int T; scanf("%d",&T);
	rep(U,T){
		int y,m,d; scanf("%d%d%d",&y,&m,&d);
		y-=1900; m--; d--;
		puts(g[y][m][d]?"YES":"NO");
	}
	return 0;
}