ABC135 C - City Savers

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os


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

    N = int(sys.stdin.readline().rstrip())
    city = list(map(int, sys.stdin.readline().split()))
    brave = list(map(int, sys.stdin.readline().split()))

    init = sum(city)
    for n in range(N):
        bef = city[n]
        city[n] -= min(city[n], brave[n])
        city[n+1] -= min(city[n+1], brave[n]-min(bef, brave[n]))

    print(init-sum(city))


if __name__ == '__main__':
    main()

考え方

各町のモンスターを倒す前の合計を算出(init)しておき、
各町のモンスターを倒す処理の後の合計と差分を出す。
差分を倒した数のモンスターとして出力を行う。

各町のモンスターを倒す処理は、

  • N人目の勇者が、Nつ目の町で倒せるだけモンスターを倒す 。
  • 残った体力で、次(N+1)の町のモンスターを倒す。

を勇者の数だけ繰り返し処理を行う。
倒せる数(brave[n])だけ、町のモンスター数の配列(city[n])から減算することで、
モンスターの数が管理しやすくなる。