SRM524 Div1 Medium

500
与えられた条件を満たすような数列で、ある区間の和とある区間の和の間に不等式が成り立つ。
長さを2分探索しながら、その関係に矛盾がないかを調べる。

難しかった。思わす解説を見た。

const int V = 100000;
int color[V];

bool rec(int curr, int size, const vector<int> &C)
{
  color[curr] = -1;
  for (int i = 0; i < C.size(); ++i) {
    int next = curr + C[i];
    if (0 <= next && next <= size) ; else continue;
    if (color[next] < 0) return false;
    if (color[next]) continue;
    if (!rec(next, size, C)) return false;
  }
  color[curr] = +1;
  return true;
}

bool make_seq(int len, const vector<int> &C)
{
  fill(color, color + V, 0);
  for (int i = 0; i <= len; ++i) {
    if (color[i]) continue;
    if (!rec(i, len, C)) return false;
  } 
  return true;
}

class LongestSequence {
public:
  int maxLength(vector <int> C)
  {
    int s = 0, b = V - 1;
    while (s + 1 < b) {
      int c = (s + b) / 2;
      if (make_seq(c, C)) s = c;
      else b = c;
    }
    return (V - 2 <= s) ? -1 : s;
  }
};