ABC048 C - Boxes and Candies

備忘録

問題

atcoder.jp

回答

import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, X = il()
    A = il()

    ret = 0
    if A[0] > X:
        ret += A[0] - X
        A[0] = X

    for n in range(N - 1):
        a = A[n] + A[n + 1]
        if a > X:
            A[n + 1] -= a - X
            ret += a - X
    print(ret)


if __name__ == '__main__':
    main()

考え方

隣り合うキャンディの合計に対して、
常にX以下となる最大値を取り続ける（貪欲法）ことで、回答を得られる。
また、キャンディを除く処理はN-1回行い、
除くキャンディは選択したn番目の箱ではなく、
次のn+1番目の箱から除く。

注意しなければならないのは1つ目の箱について。
例えば、許容される合計値X = 3、一つ目の箱にキャンディが6個、
二つ目の箱にキャンディが3個となってときなど。
二つの箱の合計が9になるため、3以下にするための最大値を2つ目の箱から取ると、
2つ目の箱は-3になる。
箱のキャンディが0未満になることはありえないので、
事前に1つ目の箱に関してはX > aの時、a = Xとしておく前処理が必要。