[BOJ 22862] 가장 긴 짝수 연속한 부분 수열 (large)

수열 $S$에서 $K$개의 원소를 임의로 삭제하였을 때, 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구하는 문제이다.

 

• 수열에서 필요한 정보는 홀짝이니, $S[i] = S[i]\ \&\ 1$로 홀수면 1, 짝수면 0으로 $S$를 초기화해주자.
• 일정 범위에서 범위를 늘리면 포함되는 홀수, 짝수는 같거나 증가한다. 줄이면 같거나 감소한다.
• 나머지는 투포인터를 이용하여 개수를 세어주면 된다.

int N, K, S[MAXN];
int main(void) {
    fastio;
    cin >> N >> K;
    for (int i = 1; i <= N; i++)
        cin >> S[i], S[i] = (S[i] & 1);
    int s = 1, e = 1;
    int cnt = S[1], ans = !S[1], tmp = !S[1];
    while (s <= e && e < N) {
        if (cnt <= K) {
            e++;
            cnt += S[e];
            tmp += !S[e];
            ans = max(ans, tmp);
        }
        while (cnt > K) {
            cnt -= S[s];
            tmp -= !S[s];
            s++;
        }
    }
    cout << ans;
    return 0;
}