ABC124 D - Handstand 解説[python]

概要

長さN のbit列があり、任意の区間に対して区間内のbitを反転させるという操作をK 回以内行うことができる。
　最良の操作を行った時、１が連続した長さの最大値を求めよ。

制約

N<=10**5
K<=10*5

考察

bit列の区間の操作の問題は他でもみる気がする（コドフォで頻出？）

ポイントはbitが同じ連続している箇所の間で区間を反転させることはメリットがないということ。(同じにならないので）

　つまり、必ずbitが異なっている箇所に区間の両端がくるようにする。

　bitが同じ連続列を1つのブロックとすると、一回操作を行うたびにブロックに隣接するブロックをつなげることができる。

k回操作を行うと2*k+1個の連続したブロックをつなげることができる。(ただし、1のブロックが端点）

　尺取で2*k+1の連続したブロックの長さの和のmaxをとると良い

実装

#!/usr/bin/env python3
# input
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, k = map(int, input().split())
s = input()
range_len = 2 * k + 1
ans = 0
block_len = []
block_len.append(0)
now = "1"
for i in s:
    if now == i:
        block_len[-1] += 1
    else:
        block_len.append(1)
        now = i
if now == "0":
    block_len.append(0)
l_block = len(block_len)
# print(block_len)
if l_block <= range_len:
    print(n)
else:
    # 尺取
    tmp = sum(block_len[:range_len])
    ans = tmp
    for idx in range(l_block - range_len):
        tmp += block_len[idx + range_len] - block_len[idx]
        # print(tmp, idx)
        if idx % 2 == 1:
            # print(ans, tmp)
            ans = max(ans, tmp)

    print(ans)

# けつにも0 をいれる。

バグらせず実装するポイント

　文字列全体を舐めるより、先にブロックの長さを計算しておいた方がよかった。

　また、先頭と末端が1ではない時に0 を挿入する。