BOJ 27651 - 벌레컷
아이디어는 그리 안어려울지 몰라도 구현이 어렵다.
a<c<b 를 만족하기 위해 a 까지의 인덱스 x를 증가시키며 y 가 될 수 있는 인덱스의 범위를 투 포인터로 좁힌다.
y 가 될 수 인덱스가 [l,r] 라고 할 때, 어떤 지점 t는 l≤t≤r 와 x+1∑t−1>t∑n−1 를 만족하는 최소 t 이고 그럼 r−t+1 이 해당 x 에서 가능한 y의 개수가 된다.
Solution 1 - Binary Search
이 t 를 이분탐색으로 찾는다. 시간 복잡도는 O(NlogN)
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;
Comments