CS Academy 084 DIV1 B - Three Ones

treeone さん...

問題へのリンク

問題概要

0 と 1 からなる長さ N の文字列 S が与えられる。

• どの連続する K 個の中にも 1 が 3 個以上含まれている

という条件を満たすような最小の K を求めよ

制約

• 3 <= N <= 10⁵
• S の中に 1 は 3 個以上含まれる

解法

右端を固定したしゃくとり法っぽくやってみた。

#include <iostream>
#include <string>
using namespace std;

int N;
string S;

int main() {
    cin >> N >> S;
    int res = -1;
    int left = 0, right = 0;
    int sum = 0;
    for (right = 0; right < S.size(); ++right) {
        sum += S[right] - '0';
        while (sum >= 3) {
            sum -= S[left] - '0';
            ++left;
        }
        res = max(res, (right+1) - (left-1));
    }
    cout << res << endl;
}