SRM524 Div1 Medium

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

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

view plainprint?

1. const int V = 100000;  
2. int color[V];  
3.   
4. bool rec(int curr, int size, const vector<int> &C)  
5. {  
6.   color[curr] = -1;  
7.   for (int i = 0; i < C.size(); ++i) {  
8.     int next = curr + C[i];  
9.     if (0 <= next && next <= size) ; else continue;  
10.     if (color[next] < 0) return false;  
11.     if (color[next]) continue;  
12.     if (!rec(next, size, C)) return false;  
13.   }  
14.   color[curr] = +1;  
15.   return true;  
16. }  
17.   
18. bool make_seq(int len, const vector<int> &C)  
19. {  
20.   fill(color, color + V, 0);  
21.   for (int i = 0; i <= len; ++i) {  
22.     if (color[i]) continue;  
23.     if (!rec(i, len, C)) return false;  
24.   }   
25.   return true;  
26. }  
27.   
28. class LongestSequence {  
29. public:  
30.   int maxLength(vector <int> C)  
31.   {  
32.     int s = 0, b = V - 1;  
33.     while (s + 1 < b) {  
34.       int c = (s + b) / 2;  
35.       if (make_seq(c, C)) s = c;  
36.       else b = c;  
37.     }  
38.     return (V - 2 <= s) ? -1 : s;  
39.   }  
40. };  

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