<AtCoder、 Python、緑色> 計算量に問題はないはずが、なぜか制限時間に間に合わないです。
解決したいこと
計算量に問題はないはずが、なぜか制限時間に間に合わないです。
<問題文>
N 人の人が左右一列に並んでいます。
0, 1 からなる長さ N の文字列 S と正整数 K が与えられます。
左から i 番目の人は、S の i 文字目が 0 のとき直立し、1 のとき逆立ちしています。
あなたは K 回まで以下の指示を行います。一度も行わなくても構いません。
指示:
1≤l≤r≤N を満たす整数
l,r を選ぶ。左から
l,l+1,...,r 番目の人の状態を反転する。すなわち、
i=l,l+1,...,r について、左から i 番目の人は直立していれば逆立ちし、逆立ちしていれば直立する。
K 回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか求めてください。
<制約>
N は 1≤N≤10^5 を満たす整数である。
K は 1≤K≤10^5 を満たす整数である。
文字列 S の長さは N である。
文字列 S の各文字は 0 または 1 である。
該当するソースコード
n, k = map(int, input().split())
#nsで0が連続する箇所と1が連続する箇所を分割する
ns = input().replace('01', '0,1').replace('10', '1,0').split(',')
def f(n):
if '0' in n:
return True
return False
#counter0で0が連続している箇所の個数を取得
counter0 = sum(map(f, ns))
#bで0が連続する箇所が最初に現れるindexを取得
b = 0 if '0' in ns[0] else 1
#eで0が連続する箇所が最後に現れるindexを取得
e = len(ns) - 1 if '0' in ns[-1] else len(ns) - 2
if counter0 < k:
print(len(''.join(ns)))
else:
#ibで逆立ちにさせる0の連続する最初のindexを取得
ib = b
#ieで逆立ちにさせる0の連続する最後のindexを取得
ie = ib+2*k-2
result = 0
#左から順に逆立ちにさせられるだけ逆立ちにし、その時に連続する最大の数を随時更新
for i in range(counter0 - k + 1):
if ie > e:
break
if ib == 0:
result = len(''.join(ns[:ie+2]))
elif ie == len(ns) - 1:
result = max(len(''.join(ns[ib-1:ie+1])), result)
else:
result = max(len(''.join(ns[ib-1:ie+2])), result)
ib += 2
ie += 2
print(result)
counter0 - k + 1 は必ず10^5以下になるはずなので、制限時間の2秒以内にループ処理が完了すると思ったのですがなぜか間に合いません。
どの辺が間違っているのかわかる方がいらっしゃったら教えてほしいです。
0
