AtCoder版蟻本中級編

DSL3C The Number of Windows

はじめに

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

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_C&lang=ja

方針

  • しゃくとり法を用います

コード

Pythonの場合、若干時間が厳しく地道な計算量削減が必要になってしまいます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
N, Q = map(int, input().split())
A = list(map(int, input().split()))
X = list(map(int, input().split()))

def two_pointers(x):
    left = 0
    sm = 0
    ans = 0
    for right in range(N):
        sm += A[right]
        while(sm > x):
            sm -= A[left]
            left += 1
        ans += (right-left+1) # leftに対する条件を満たすパターン数
    return ans

for x in X:
    print(two_pointers(x))

記事情報

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