ARC 040 B - 直線塗り（2015/06/13）

問題

B: 直線塗り - AtCoder Regular Contest 040 | AtCoder

回答

Submission #425622 - AtCoder Regular Contest 040 | AtCoder

基本的に足場が"."だった時に塗るっていう貪欲で処理で良いが，一番右の"."を塗る際だけ，少し別途処理．なぜなら最後だけ一番右側-R+1のところから発射すれば濡れるからですね．うん．

なお，本番では最後の方の処理をごまかしていたためにWAして通らなかった模様．
通らないケースが想定できないので，他の人のコードを元に完成させました…．

N, R = map(int, input().split())
data = input()
 
idx, res = 0, 0
last = data.rfind(".")
while N > data.count("o"):
	res += 1
	if data[idx] == "." or idx > last-R:
		next = min(idx+R, N)
		data = data[:idx] + data[idx:next].replace(".", "o") + data[next:]
	else:
		idx += 1
print(res)