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; }