水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

ARC 040 B - 直線塗り(2015/06/13)

回答

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)