BOJ 27651 - 벌레컷

BOJ 27651 - 벌레컷

아이디어는 그리 안어려울지 몰라도 구현이 어렵다.

$a<c<b$ 를 만족하기 위해 $a$ 까지의 인덱스 $x$를 증가시키며 $y$ 가 될 수 있는 인덱스의 범위를 투 포인터로 좁힌다.

$y$ 가 될 수 인덱스가 $[l,\,r]$ 라고 할 때, 어떤 지점 $t$는 $l\le t \le r$ 와 $\displaystyle\sum_{x+1}^{t-1}>\sum_t^{n-1}$ 를 만족하는 최소 $t$ 이고 그럼 $r-t+1$ 이 해당 $x$ 에서 가능한 $y$의 개수가 된다.

Solution 1 - Binary Search

이 $t$ 를 이분탐색으로 찾는다. 시간 복잡도는 $O(N\log N)$

void solve() {  
   int n;  
   cin >> n;  
   vi a(n);  
   fv(a);  
   vi psum(n + 1);  
   for (int i = 0; i < n; i++) psum[i + 1] = psum[i] + a[i];  
   auto q = [&](int l, int r) {  
      if (l > r) return 0ll;  
      return psum[r + 1] - psum[l];  
   };  
   int ans = 0;  
   for (int x = 0, y_start = 1, y_end = n - 2, y_mid = 1; x < n - 2; x++) {  
      int A = q(0, x);  
  
      y_start = max(y_start, x + 1);  
      while (y_end > 0 && q(y_end + 1, n - 1) <= A) y_end--;  
      while (y_start < n && q(y_start, y_end) <= A) y_start++;  
  
      if (y_start > y_end) break;  
  
      int l = y_start, r = y_end;  
      int t = -1;  
      while (l <= r) {  
         int m = l + r >> 1;  
         if (q(x + 1, m) > q(m + 1, n - 1)) {  
            t = m;  
            r = m - 1;  
         } else l = m + 1;  
      }  
      if (t != -1)  
         ans += max(0ll, y_end - t + 1);  
   }  
   cout << ans;  
}

Solution 2 - Only Two-Pointer

$l$ 과 $r$ 을 $r$을 먼저 좁힌후에 $l$ 을 좁혀나가면 투 포인터로만 구간을 관리할 수 있어 $t$ 를 찾을 필요가 없다. $l$ 이 $t$ 자체가 되기 때문이다.

이 방법은 $O(N)$ 으로 문제를 해결할 수 있다.

$l$ 이 커진다는 것은 중간 구간이 길어진다는 것을 의미한다.

int n;  
cin >> n;  
vi a(n);  
fv(a);  
vi psum(n + 1);  
for (int i = 0; i < n; i++) psum[i + 1] = psum[i] + a[i];  
auto q = [&](int l, int r) {  
   if (l > r) return 0ll;  
   return psum[r + 1] - psum[l];  
};  
int ans = 0;  
for (int x = 0, l = 1, r = n - 2; x < n - 2; x++) {  
   int A = q(0, x);  
  
   l = max(l, x + 1);  
   while (r > 0 && q(r + 1, n - 1) <= A) r--;  
   while (l < n && q(x + 1, l) <= q(l + 1, n - 1)) l++;  
   ans += max(0ll, r - l + 1);  
}  
cout << ans;