SRM495 Div1 Easy

275

memo[どこまで見た][最後に使った数] = 最後まで作りきれるかどうか
バックトラックしていたら終わらないので、到達可能かどうかをメモ化する。
到達可能と判断できた瞬間にそれまでのパスをなぞる。

const int undef = -100;
vector<int> result;

const int K = 50 + 1;
const int M = 1000 + 1;

bool prime[M];

const int fail = 0;
const int succ = 1;

int memo[K][M];
int buff[K];

string C;

bool rec(int nth, int last, const int N)
{
  if (nth == C.size()) return succ;
  int& ret = memo[nth][last];
  if (ret != -1) return ret;
  ret = fail;
  for (int next = last + 1; next <= N; ++next) {
    if ((C[nth] == 'R' &&  prime[next]) ||
        (C[nth] == 'B' && !prime[next])) {
      buff[nth] = next;
      if (rec(nth + 1, next, N) == succ) {
        ret = succ;
        for (int i = 0; i <= nth; ++i) {
          if (result[i] == undef) result[i] = buff[i];
          else if (result[i] != buff[i]) result[i] = -1;
        }
      }
    }
  }
  return ret;
}

class ColorfulCards {
public:
  vector <int> theCards(int N, string c)
  {
    C = c;

    fill(prime, prime + M, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i * i < M; ++i) {
      for (int j = 2; i * j < M; ++j) {
        prime[i * j] = false;
      }
    }

    result.resize(c.size());
    fill(result.begin(), result.end(), undef);
    fill(&memo[0][0], &memo[K - 1][M - 1] + 1, -1);
    rec(0, 0, N);
    return result;
  }
};