https://kyopro.hateblo.jp/entry/2019/04/14/115238

問題. Handstand

長さ $N$ の 0 と 1 からなる文字列 $S$ と非負整数 $K$ が与えられる． $S$ の連続する区間を任意に選び，その区間に含まれる 0 と 1 を反転するという操作を高々 $K$ 回行う．そのとき，連続する1 からなる区間の長さの最大値を答えよ．

制約： $1 \le N, K \le 10^5$

解法．尺取り法

選択することのできる区間の数は $\binom{N}{2}$ 個あり，その内から $K$ 個以下の区間を選んでシミュレーションをするのでは間に合わない．まず，同じ区間を複数回選ぶのは無駄であることが分かる．また，交わる区間を選ばないという制約を加えても最大値には影響を与えない．また，連続する 0 からなる区間は，その内の1要素を変更するなら区間内のすべての要素を 1 に変更したほうが良いことが分かる．
$i$ 番目の要素が 1 からなる連続する区間の左端としたときに， $K$ 回以内の操作で最も右端にすることができる添字を $f(i)$ とする．ここで，任意の $1 \le j \le N$ に対してそのような $f(j)$ を構成できたとき， $f(1) \le f(2) \le \ldots \le f(N)$ という関係から尺取り法で $O(N)$ 時間で最大の長さを求めることができる．
上の観察から，区間 $[i, \,f(i) ]$ 内の連続する 0 からなる部分区間の数は $K$ 個以下であることが分かる．したがって， $S_i$ が 1，または， $S_i$ が 0 かつ $S_{i + 1}$ が 0 ならば $f(i) = f(i + 1)$ となる．それ以外の場合，すなわち $S_i$ が 0 で $S_{i + 1}$ が 1 の場合は $S_i$ を 1 にするために操作を 1 回行わないといけない．このとき，操作の回数が $K$ 回を超えたら右端の候補を $f(i + 1)$ から始めて，連続する 0 からなる最も右側にある区間 $[l, \, r]$ を探し，その区間を反転せずに， $f(i) = l - 1$ とする．

計算時間： $O(N)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    int max_len = 1;
    int last = n - 1, num_zero = (s.back() == '0');
    for (int first = n - 2; 0 <= first; --first) {
        if (s[first] == '1'
            || (s[first] == '0' && s[first + 1] == '0')) {
            max_len = max(max_len, last - first + 1);
        }
        else {
            ++num_zero;
            while (k < num_zero) {
                while (s[last] == '1') --last;
                while (s[last] == '0') --last;
                --num_zero;
            }
            max_len = max(max_len, last - first + 1);
        }
    }

    cout << max_len << endl;

    return 0;
}

オンラインで参加できなかったので復習した．順位表を見たけどみんな速すぎでビビる．しかも，D問題解けている人数が多いのもビビる．