SRM520 Div2 Hard

1000
メモ化する。直前の1行を覚えておけばいい。

const int mod = 1000000007;

const int N = 50 + 1;
const int M = 3 + 1;
map<string, lli> memo[N];

bool cmp(string a, string b)
{
  int a_pass = count(a.begin(), a.end(), 'P');
  int b_pass = count(b.begin(), b.end(), 'P');
  if (a_pass > b_pass) return true;

  int a_chal = count(a.begin(), a.end(), 'C');
  int b_chal = count(b.begin(), b.end(), 'C');
  if (a_pass == b_pass && a_chal <= b_chal) return true;

  return false;
}

lli rec(int n, string prev, const vector<string> &D)
{
  if (n < 0) return 1;
  if (memo[n].count(prev)) return memo[n][prev];

  const int Y = count(D[n].begin(), D[n].end(), 'Y');

  const string s = "PCFN";
  string t = "@@@";

  lli sum = 0;

  for (int a = 0; a < s.size(); ++a) {
    if (D[n][0] == 'N' || s[a] == 'N') if (D[n][0] != s[a]) continue;
    for (int b = 0; b < s.size(); ++b) {
      if (D[n][1] == 'N' || s[b] == 'N') if (D[n][1] != s[b]) continue;
      for (int c = 0; c < s.size(); ++c) {
        if (D[n][2] == 'N' || s[c] == 'N') if (D[n][2] != s[c]) continue;

        t[0] = s[a];
        t[1] = s[b];
        t[2] = s[c];

        int pass = count(t.begin(), t.end(), 'P');
        int chal = count(t.begin(), t.end(), 'C');
        int fail = count(t.begin(), t.end(), 'F');

        if (pass + chal + fail == Y && cmp(t, prev) ) {
          sum = (sum + rec(n - 1, t, D)) % mod;
        }
      }
    }
  }
  return memo[n][prev] = sum;
}

class SRMSystemTestPhase {
public:
  int countWays(vector <string> D)
  {
    fill(memo, memo + N, map<string, lli>());
    return rec((int)D.size() - 1, "CCC", D);
  }
};