公式
B - Corridor Watch 解説 by en_translator
A cell is not watched if and only if there is no guardman on a cell distant by at most \(D\). Therefore, the number of cells that are not watched can be counted by checking for each cell if there is no cell with a guardman within the distance up to \(D\).
m, d = map(int, input().split())
s = input()
ans = 0
for x in range(m):
ok = False
for i in range(m):
ok |= s[i] == "G" and abs(x - i) <= d
ans += not ok
print(ans)
Bonus: solve the problem under the constraints \(1\le D\le N\le 5\times 10^5\). (Worth ABC-C)
投稿日時:
最終更新: