11/22 Subsequence

문제

링크: 11/22 Subsequence
난이도: 1396

풀이

어떤 /의 위치 $i$ 에 대해 이보다 왼쪽에 있는 $1$ 의 개수를 $o$ , 오른쪽에 있는 $2$ 의 개수를 $t$ 라 합시다.

그렇다면 $i$ 를 중심으로 하는 부분 11/22 문자열의 최대 길이는 $2\min(o, t) + 1$ 이 됩니다.

이때 $i$ 가 증가하면 $o$ 는 증가하고 $t$ 는 감소하므로 $\min(o, t)$ 는 $i$ 가 증가함에 따라 증가하다가 감소하는 형태를 띕니다.

따라서 $o \leq t$ 를 만족하는 가장 오른쪽에 있는 /, 혹은 $o \geq t$ 를 만족하는 가장 왼쪽에 있는 /만 검사하면 최댓값을 찾을 수 있습니다.

이때 조건 $o \leq t$ 는 단조성을 띄므로 이분 탐색을 통해 해당 /의 위치를 찾을 수 있습니다.

누적 합을 미리 전처리한 다음 이분 탐색을 이용해 후보를 찾으면 쿼리마다 $O(\log N)$ 에 답할 수 있습니다.

따라서 $O(N + Q\log N)$ 에 문제를 해결할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;
 
#define all(v) v.begin(), v.end()
 
int cnt[101010][2];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, Q;
    cin >> N >> Q;
 
    string S;
    cin >> S;
    S = "#" + S;
 
    vector<int> slashes;
 
    for (int i = 1; i <= N; i++) {
        cnt[i][0] = cnt[i - 1][0];
        cnt[i][1] = cnt[i - 1][1];
 
        if (S[i] == '/') {
            slashes.push_back(i);
            continue;
        }
 
        int num = S[i] - '1';
        cnt[i][num] += 1;
    }
 
    for (int q = 0; q < Q; q++) {
        int L, R;
        cin >> L >> R;
 
        int l = lower_bound(all(slashes), L) - slashes.begin();
        int r = upper_bound(all(slashes), R) - slashes.begin() - 1;
 
        if (r < l) {
            cout << 0 << '\n';
            continue;
        }
 
        int lo = l, hi = r;
        while (lo < hi) {
            int m = (lo + hi) / 2;
 
            int i = slashes[m];
 
            if (cnt[i][0] - cnt[L - 1][0] < cnt[R][1] - cnt[i][1]) lo = m + 1;
            else hi = m;
        }
 
        int i = slashes[lo];
        int half = min(cnt[i][0] - cnt[L - 1][0], cnt[R][1] - cnt[i][1]);
 
        if (l <= lo - 1) {
            i = slashes[lo - 1];
            half = max(half, min(cnt[i][0] - cnt[L - 1][0], cnt[R][1] - cnt[i][1]));
        }
 
        cout << 2*half + 1 << '\n';
    }
 
    return 0;
}

풀이

어떤 /의 위치

i

에 대해 이보다 왼쪽에 있는

1

의 개수를

o

, 오른쪽에 있는

2

의 개수를

t

라 합시다.

그렇다면

i

를 중심으로 하는 부분 11/22 문자열의 최대 길이는

2\min(o, t) + 1

이 됩니다.

이때

i

가 증가하면

o

는 증가하고

t

는 감소하므로

\min(o, t)

는

i

가 증가함에 따라 증가하다가 감소하는 형태를 띕니다.

따라서

o \leq t

를 만족하는 가장 오른쪽에 있는 /, 혹은

o \geq t

를 만족하는 가장 왼쪽에 있는 /만 검사하면 최댓값을 찾을 수 있습니다.

이때 조건

o \leq t

는 단조성을 띄므로 이분 탐색을 통해 해당 /의 위치를 찾을 수 있습니다.

누적 합을 미리 전처리한 다음 이분 탐색을 이용해 후보를 찾으면 쿼리마다

O(\log N)

에 답할 수 있습니다.

따라서

O(N + Q\log N)

에 문제를 해결할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;
 
#define all(v) v.begin(), v.end()
 
int cnt[101010][2];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, Q;
    cin >> N >> Q;
 
    string S;
    cin >> S;
    S = "#" + S;
 
    vector<int> slashes;
 
    for (int i = 1; i <= N; i++) {
        cnt[i][0] = cnt[i - 1][0];
        cnt[i][1] = cnt[i - 1][1];
 
        if (S[i] == '/') {
            slashes.push_back(i);
            continue;
        }
 
        int num = S[i] - '1';
        cnt[i][num] += 1;
    }
 
    for (int q = 0; q < Q; q++) {
        int L, R;
        cin >> L >> R;
 
        int l = lower_bound(all(slashes), L) - slashes.begin();
        int r = upper_bound(all(slashes), R) - slashes.begin() - 1;
 
        if (r < l) {
            cout << 0 << '\n';
            continue;
        }
 
        int lo = l, hi = r;
        while (lo < hi) {
            int m = (lo + hi) / 2;
 
            int i = slashes[m];
 
            if (cnt[i][0] - cnt[L - 1][0] < cnt[R][1] - cnt[i][1]) lo = m + 1;
            else hi = m;
        }
 
        int i = slashes[lo];
        int half = min(cnt[i][0] - cnt[L - 1][0], cnt[R][1] - cnt[i][1]);
 
        if (l <= lo - 1) {
            i = slashes[lo - 1];
            half = max(half, min(cnt[i][0] - cnt[L - 1][0], cnt[R][1] - cnt[i][1]));
        }
 
        cout << 2*half + 1 << '\n';
    }
 
    return 0;
}

11/22 Subsequence

문제

풀이

코드

댓글

11/22 Subsequence

문제

풀이

코드

댓글