連続する整数
- 尺取法を改良して
O(2N)で計算できる
colab
実装
A = [2,3,4, 6,7, 9, 11,12, 15] # 5個のグループ
cnt = 0
i, j = 0, 0
while i < len(A)-1 and j < len(A)-1:
if i == j:
i += 1
cnt += 1
elif A[i] + 1 == A[i+1]:
i += 1
elif A[i] + 1 != A[i+1]:
j += 1
print(cnt) # 5
例; 連続する区間の総数を出す
問題
解説
- 右からの累積和、左からの累積和、上からの累積和、下からの累積和で計算できる
解答
H,W = map(int,input().split())
G = [list(input()) for _ in range(H)]
D = dict()
for tp in ["u", "d", "l", "r"]:
D[tp]=[[0]*W for i in range(H)]
for i in reversed(range(H)):
for j in range(W):
if G[i][j]=='.' and i<H-1:
D["u"][i][j]=D["u"][i+1][j]+1
elif G[i][j]=='.':
D["u"][i][j]=1
for i in range(H):
for j in range(W):
if G[i][j]=='.' and i>0:
D["d"][i][j]=D["d"][i-1][j]+1
elif G[i][j]=='.':
D["d"][i][j]=1
for i in range(H):
for j in reversed(range(W)):
if G[i][j]=='.' and j<W-1:
D["l"][i][j]=D["l"][i][j+1]+1
elif G[i][j]=='.':
D["l"][i][j]=1
for i in range(H):
for j in range(W):
if G[i][j]=='.' and j>0:
D["r"][i][j]=D["r"][i][j-1]+1
elif G[i][j]=='.':
D["r"][i][j]=1
ans=0
for i in range(H):
for j in range(W):
ans=max(ans,D["u"][i][j]+D["d"][i][j]+D["l"][i][j]+D["r"][i][j]-3)
print(ans)