BOJ 2855 - 흥미로운 수열

BOJ 2855 - 흥미로운 수열

어려운 문제였다.

그냥 이분탐색을 써서 $S$ 가 넘지 않는 지점을 찾은다음 범위를 좁혀주는 방식으로 $O(n^2)$ 에도 풀렸지만 원래 해답은 다음과 같이 풀 수 있다.

$i$에서 왼쪽으로 최대로 합이 $s$ 이하인 곳을 $L$ 이라고 하고, $i+1$ 에서 오른쪽으로 최대로 합이 $s$ 이하인 곳을 $R$ 이라 하자.

그럼 $i-\text{Min}(R_{i+1}-(i+1), i-L_i)+1$ 는 $\text{Min}(R_{i+1}-i-1,i-L_i)$ 으로 마킹을 해줄 수 있다.

어떤 구간의 시작이 아닌 중앙에서부터 본 것이다.

이렇게 모두 인덱스에 마킹을 해두었다면 이 값들을 $b_i$ 라고 하자.

$b_i=k$ 라면 $i$ 에서의 정답은 $2k$가 되고 $i+1$ 에서의 정답은 최소 $2k-2$ 가 됨을 관찰한다.

투포인터로 $b$ 를 구해주면 $O(n)$ 에 풀 수 있다.

void solve() {
   int n, s;
   cin >> n >> s;
   vi a(n);
   fv(a);
   vi L(n), R(n);

   for (int i = 0, j = 0, sum = 0; i < n; i++) {
      sum += a[i];
      L[i] = R[i] = -1;
      while (j <= i && sum > s) sum -= a[j], j++;
      L[i] = j;
   }
   for (int i = n - 1, j = n - 1, sum = 0; i >= 0; i--) {
      sum += a[i];
      while (j >= i && sum > s) sum -= a[j], j--;
      R[i] = j;
   }
   vi ans(n * 2);
   for (int i = 0; i < n - 1; i++) {
      if (L[i] <= i && R[i + 1] >= i + 1) {
         int len = min(R[i + 1] - i, i - L[i] + 1);
         ans[i - len + 1] = len * 2;
      }
   }
   for (int i = 1; i < n; i++) {
      maxa(ans[i], ans[i - 1] - 2);
   }
   for (int i = 0; i < n; i++) cout << ans[i] << endl;
}