ABC229D - Longest X

考え方

左端と右端を右方向に動かしていけば，$S$の長さの2倍の計算量で全て見ていける．

したがって，しゃくとり法で実装すれば良い．あとは，いかにバグらせないかがポイントになる．

回答例. 1

$X$に変えられる区間$[l, r)$を管理する．区間の長さは$r - l$で計算できる．

右端の$r$は含まないようにするのがポイント．また，初期状態は空集合になっている．

S = input()
K = int(input())

N = len(S)
l, r = 0, 0
num_dot = 0
ans = 0
while l < N:
  while r < N and (S[r] == 'X' or num_dot < K):
    if S[r] == '.':
      num_dot += 1
    r += 1
  ans = max(ans, r - l)
  if S[l] == '.':
    num_dot -= 1
  l += 1
  
print(ans)

回答例. 2 - dequeを使う

添字を使うとバグりやすい．そこで，dequeで直接区間を管理するとバグりにくくできる．

1つ目の方法では，左側から動かしていき，右側は条件を超えないように動かした．

今度は右側から動かしていき，条件を破った分を左側から除いていく．

from collections import deque

S = input()
K = int(input())

N = len(S)
que = deque()
num_dot = 0
ans = 0
for r in S:
  que.append(r)
  if r == '.':
    num_dot += 1
  while num_dot > K:
    l = que.popleft()
    if l == '.':
      num_dot -= 1
  ans = max(ans, len(que))

print(ans)