F - More Holidays Editorial by evima
原案者の実装公式解説とほとんど同じですが、二分探索と始点の全探索の順序を逆にすることもできます。この場合、始点が左端の場合のみ x
を素直に数えれば、以降は始点を一つずつ動かした際に新しく区間に入る一文字と出ていく一文字に注目するだけで個数を計算できます。
実装例 (Python)
N, M, K = map(int, input().split())
S = input()
lo, hi = K, N * M + 1
while lo + 1 < hi:
mi = (lo + hi) // 2
x = S.count('x') * (mi // N) + S[: mi % N].count('x')
ok = False
for i in range(N):
ok |= x <= K
if mi + i >= N * M:
break
x += S[(mi + i) % N] == 'x'
x -= S[i] == 'x'
if ok:
lo = mi
else:
hi = mi
print(lo)
posted:
last update: