公式

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\).

Sample code (Python 3)

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)

投稿日時:
最終更新: