数の和


作成日:2022年1月11日午後4:58

インプリメンテーションコード

# 수들의 합
import sys
sys.stdin = open("input.txt", "rt")
n, m = map(int, input().split())
l = list(map(int,input().split()))
result = 0

for i in range(0, n):
    sum = l[i]
    j = i+1
    while True:
        if sum == m:
            result += 1
            break
        elif sum < m and j < n:
            sum += l[j]
            j += 1
        else:
            break

print(result)

模範解答

import sys
sys.stdin = open("input.txt", 'r')
n, m=map(int, input().split())
a=list(map(int, input().split()))
lt=0
rt=1
tot=a[0]
cnt=0
while True:
    if tot<m:
        if rt<n:
            tot+=a[rt]
            rt+=1
        else:
            break
    elif tot==m:
        cnt+=1
        tot-=a[lt]
        lt+=1
    else:
        tot-=a[lt]
        lt+=1
print(cnt)

差異

  • 私が実装したコードでは、与えられた配列が大きい場合、タイムアウトエラーとして処理される.
  • why?
  • 私は一度繰り返した時に、初めて指定したものを基準に、連続したものを加えて、mより大きければ計算した値を全部捨てて、次のものの方式を再チェックします.
  • 模範解答では、基準項目と連続項目の和がmより大きい場合、基準項目をtotから削除し、次の項目を基準として検査する.△totをあきらめない.
  • は、同じ機能を完了しながら時間を節約することができる.
  • why?
    例えば、2 2 2 3 1 2アレイが与えられた場合、

  • 連続
  • のアイテムの和が5(=m)の場合、最初の基準アイテムは2となります.その後続行すると、tot=2+2+3=7が5を超え、対応するデータム項目は連続する項目を追加する際に5を作成できないため、次の項目をデータム項目として再検査する必要がある.この場合、tot値は0に初期化され、再度繰り返し文で確認しても同様の機能があるが、tot値の既存の基準項目から2を減算した値、すなわち、5をtotとして保持し、次の基準項目をチェックしても同様の機能を保持する.3番目の位置に追加された理由は、それまでのアイテムの和が5以下であったため、これは当然次のアイテムを起点としており、それに加えて、同じ5以下を作り出すことになる.