POJ 1082 - Calendar Game

http://poj.org/problem?id=1082

概要

与えられた日付からスタートして、2人のプレイヤーが交互に

のいずれかを行って、2011/11/4 以降に移動したほうが勝ちだとする。 両プレイヤーが最適の手を選んだとき、先手が勝つかどうかを答える。

制約

解法

範囲がそれほど大きくないのでメモりながら普通にゲーム木探索するだけ。

  1 #include <iostream>
  2 using namespace std;
  3 static const int YEAR = 2001-1900, MON = 11, MDAY = 4;
  4 
  5 bool overrun(int year, int mon, int mday)
  6 {
  7   if (year > YEAR) {
  8     return true;
  9   } else if (year < YEAR) {
 10     return false;
 11   }
 12   if (mon > MON) {
 13     return true;
 14   } else if (mon < MON) {
 15     return false;
 16   }
 17   if (mday > MDAY) {
 18     return true;
 19   }
 20   return false;
 21 }
 22 
 23 bool leap(int y)
 24 {
 25   y += 1900;
 26   if (y % 400 == 0) {
 27     return true;
 28   } else if (y % 100 == 0) {
 29     return false;
 30   } else if (y % 4 == 0) {
 31     return true;
 32   } else {
 33     return false;
 34   }
 35 }
 36 
 37 int days(int y, int m)
 38 {
 39   static const int t[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
 40   if (m == 2) {
 41     return t[m] + leap(y);
 42   } else {
 43     return t[m];
 44   }
 45 }
 46 
 47 void fix(int& y, int& m, int& d)
 48 {
 49   if (d > days(y, m)) {
 50     d = 1;
 51     ++m;
 52   }
 53   if (m > 12) {
 54     m = 1;
 55     ++y;
 56   }
 57 }
 58 
 59 int memo[YEAR+1][13][40];
 60 
 61 bool solve(int year, int mon, int mday)
 62 {
 63   if (year == YEAR && mon == MON && mday == MDAY) {
 64     return false;
 65   } else if (overrun(year, mon, mday)) {
 66     throw "err";
 67   } else {
 68     int& ans = memo[year][mon][mday];
 69     if (ans != -1) {
 70       return ans;
 71     }
 72     int y = year, m = mon, d = mday+1;
 73     fix(y, m, d);
 74     if (!solve(y, m, d)) {
 75       return ans = true;
 76     }
 77     y = year, m = mon+1, d = mday;
 78     fix(y, m, d);
 79     if (d == mday && !overrun(y, m, d) && !solve(y, m, d)) {
 80       return ans = true;
 81     }
 82     return ans = false;
 83   }
 84 }
 85 
 86 int main()
 87 {
 88   for (int i = 0; i <= YEAR; i++) {
 89     for (int j = 1; j <= 12; j++) {
 90       for (int k = 1; k < 40; k++) {
 91         memo[i][j][k] = -1;
 92       }
 93     }
 94   }
 95   int T;
 96   cin >> T;
 97   while (T-- > 0) {
 98     int y, m, d;
 99     cin >> y >> m >> d;
100     y -= 1900;
101     cout << (solve(y, m, d) ? "YES" : "NO") << endl;
102   }
103   return 0;
104 }
poj/1082.cc