ABC124 D - Handstand

考えたこと

・010を[1,3]で反転させると101、[2,2]を反転させて 111 とできるが、

これは左の０と右の０を別々に反転させることと同じっぽい。

（１を跨いで反転させるのは無意味そう）

・連続する０を反転することだけを考えればいいのではないか？

・（連続する０の区間）からＫ個の区間を反転させると考えると、離れた区間同士を反転させても、最大にはならなさそう。

・隣同士の区間を反転させていく「貪欲法」が成立する？

・一番左の０の区間を選べば、そこからＫ個のゼロの区間は一意に定まる。

（そこから順番にＫ個右に取っていけばいい）

・前処理をすれば右端はlower_boundで求まりそう！解けた！

結果

・実装でバグが大発生。

・１時間３０分椅子を温めた。

いろいろ見た結果

・尺取り法が一番綺麗そう。

・それはそうで、よく考えると

「連続した０の区間の個数は、区間に対して単調増加する」

ので尺取り法がつかえる。

（「にぶたん大好きマン」なのでついつい二分探索をしてしまう。悪癖である。）

重要ポイント

・右端ｒが１から０に移り変わるとき、連続した０の区間の個数contは１増える。

・左端ｌが０から１に移り変わるとき、連続した０の区間の個数contは１減る。

・一番左の部分が０から始まる場合、cont=1で始めないといけない。

（理由：contが増えるのは左端が１から０に増えるときだが、一番左より左には文字はない。）

実装

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  string s;
  cin >> s;

  int ans = 0, r = 0, cont = 0;

  if (s[0] == '0') cont++;

  for (int l = 0; l < N; l++) {

    while (cont <= K && r < N) {
      if (r + 1 < N && s[r] == '1' && s[r + 1] == '0') cont++;
      r++;
    }

    ans = max(ans, r - l);

    if (l + 1 < N && s[l] == '0' && s[l + 1] == '1') cont--;
  }

  cout << ans << endl;
  return 0;
}

我ながら美しいコードである。（自分で言うな）

感想：

結果としては３完だった。

悔しい。悔しい。悔しい。

もっと強くなりたい。

精進します。