しゃくとり法の実装
ポイント
$ [L, R)の半開区間で考える
$ Lは$ 1つずつ動かす。$ Rを伸ばせるだけ伸ばす
実際に加える前に、$ Rを増やしても条件を満たすか確認する
$ Lを狭める時に長さ$ 0の区間か確認する
$ Lが$ Rを追い越さないようにする
code: shakutori.py
class shakutori():
def __init__(self, A):
self.A = A
self.N = len(A)
self.R = 0
# ansの初期値や区間を管理する変数を定義する
self.ans = 0
# xを追加しても条件を満たすか
def __is_ok(self, x):
return
def __add_element(self, x):
return
def __remove_element(self, x):
return
# 半開区間[L, R)は条件を満たす
def __update_ans(self, L, R):
return
def get_ans(self):
for L in range(self.N):
while self.R < self.N:
if self.__is_ok(self.Aself.R): self.__add_element(self.Aself.R) self.R += 1
else: break
self.__update_ans(L, self.R)
if L < self.R:
self.__remove_element(self.AL) else:
self.R = L+1
return self.ans
使用例
code: b229d.py
class shakutori():
def __init__(self, A):
self.A = A
self.N = len(A)
self.R = 0
# ansの初期値や区間和などの変数を定義する
self.ans = 0
self.C = 0
# xを追加しても条件を満たすか
def __is_ok(self, x):
return self.C + (x == ".") <= K
def __add_element(self, x):
if x == ".":
self.C += 1
return
def __remove_element(self, x):
if x == ".":
self.C -= 1
return
def __update_ans(self, L, R):
self.ans = max(self.ans, R - L)
return
def get_ans(self):
for L in range(self.N):
while self.R < self.N:
if self.__is_ok(self.Aself.R): self.__add_element(self.Aself.R) self.R += 1
else: break
self.__update_ans(L, self.R)
if L < self.R:
self.__remove_element(self.AL) else:
self.R = L+1
return self.ans
S = input()
K = int(input())
sk = shakutori(S)
print(sk.get_ans())