PAST4D
from 第四回 アルゴリズム実技検定
PAST4D
考えたこと
空欄を端から埋めていく問題
端に接触してる空欄があるならその長さは最低限必要
空欄の個数を数える
補足: 最長の空欄が、両端の空欄を足したものの以下なら、両端の空欄を埋めるように動けばそれで十分埋まる
補足
公式解説
50×50なので全探索しても良い
pythondef solve(N, S):
spaces = []
if S[0] == ord("#"):
spaces.append(0)
state = "BLOCK"
else:
state = "SPACE"
c = 0
for i in range(N):
if state == "SPACE":
if S[i] == ord("."):
c += 1
else:
spaces.append(c)
state = "BLOCK"
else:
if S[i] == ord("."):
state = "SPACE"
c = 1
else:
pass
if state == "BLOCK":
spaces.append(0)
else:
spaces.append(c)
m = max(spaces)
if m > spaces[0] + spaces[-1]:
print(spaces[0], m - spaces[0])
else:
print(spaces[0], spaces[-1])Related Pages
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]