ABC130 D - Enough Array
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time # 時々使う # import numpy as np # from decimal import Decimal, ROUND_HALF_UP # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) # MOD = 10 ** 9 + 7 MOD = 998244353 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, K = il() A = il() ret, sm, r = 0, 0, 0 for l in range(N): while r < N and sm < K: sm += A[r] r += 1 if sm < K: break ret += N - r + 1 sm -= A[l] print(ret) if __name__ == '__main__': main()
考え方
尺取り法で和がK
以上になる区間を求めます。
- 回答概要
- 右端と左端を設定する
- 設定した範囲の和を求める
- 右端と左端がインクリメントするとき、合計値を再計算する
典型的な尺取り法を用いる問題です。
まず、正整数列A
に対して、左端l
と右端r
を設定します。
l
とr
を0
から始め、r
をインクリメントして配列A
の右端を広げて、
範囲の和がK
以上となるまで範囲を順次広げます。
範囲の和がK
を上回る時点で、r
のインクリメントを終了します。
範囲l, r
の和がK
を上回るとき、A
は正の整数のみで構築されているため、
r
以上N
以下の範囲は全てK
を上回ることが分かります。
和がK
以上となる範囲が求まった後は、l
のインクリメントを行います。
l
のインクリメントを行うと、左端の位置が一つ進むので、
合計値から範囲から外れた値を減算します。
その後、再び範囲の和がK
を上回るまでr
のインクリメントを進めて、
K
を上回った時点のr
からN
までの範囲を記録します。
繰り返し、l
とr
を進めて順次、K
を上回る範囲を求めることで回答を求めること出来ます。