公式

B - Corridor Watch 解説 by sounansya


あるマスが監視されていない条件は「そのマスと距離が \(D\) 以下のマスにガードマンがいない」です。したがって、各マスに対しそのマスと距離が \(D\) 以下のマスにガードマンがいないかを愚直に判定することでガードマンに監視されていないマスの個数を求めることができます。

実装例(Python3)

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 程度)

投稿日時:
最終更新: