AtCoder Beginner Contest 048 C – Boxes and Candies をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Beginner Contest 048 C – Boxes and Candies

端から順に決めていける問題。貪欲に行こう。

# AtCoder Beginner Contest 048 C - Boxes and Candies
# https://atcoder.jp/contests/abc048/tasks/arc064_a
# tag: 貪欲法 すぬけ君

# 左端から連続する2つをセットに順に見ていき、必要な数だけ
# 食べていく。ただし、セットのうちなるべく右側から食べる。

# という貪欲法で解ける。
# つまり、可能な限り次の操作が有利になるような食べ方を
# していく、ということ。

def main():
    N, x = map(int, input().split())
    candies = list(map(int, input().split()))

    result = 0

    for i in range(N-1):
        # 隣り合う 2個セットで確認する。
        former, latter = candies[i], candies[i+1]
        if former + latter <= x:
            continue

        must_eat = former + latter - x
        result += must_eat

        # なるべく右から食べる。
        if latter >= must_eat:
            candies[i+1] -= must_eat
        else:
            must_eat -= candies[i+1]
            candies[i+1] = 0
            candies[i] -= must_eat

    print(result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。