ABC032C 列

はじめに

カテゴリーAtCoder版蟻本中級編では、AtCoder 版!蟻本 (中級編)でまとめられている問題をPythonで解いています。

問題

https://atcoder.jp/contests/abc032/tasks/abc032_c

方針

  • しゃくとり法を用います
  • leftを移動する際に、A[left]で割る必要があるためゼロ除算に注意が必要です
  • この問題ではA0が含まれる場合、答えが明らかにNなので、最初に条件分岐してしまえば良いです。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
N, K = map(int, input().split())
A = []
for n in range(N):
a = int(input())
A.append(a)

if 0 in A:
print(N)
exit()

right = 0
sm = 1
ans = 0
for left in range(N):

while(right<N and sm*A[right]<=K): # rightをインクリメントでs切るか確認
sm *= A[right]
right += 1

ans = max(ans,right-left) # leftに対する条件を満たすパターン数
if (left == right): # leftがrightを超えないようにする
right += 1
else:
sm /= A[left] # leftの移動準備

print (ans)

記事情報

  • 投稿日:2020年5月10日
  • 最終更新日:2020年5月10日