公式
B - Corridor Watch 解説
by
B - Corridor Watch 解説
by
sounansya
あるマスが監視されていない条件は「そのマスと距離が \(D\) 以下のマスにガードマンがいない」です。したがって、各マスに対しそのマスと距離が \(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:制約を \(1\le D\le N\le 5\times 10^5\) で解いてみてください。(ABC - C 程度)
投稿日時:
最終更新:
