ARC056 A - みんなでワイワイみかん

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# 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")

    A, B, K, L = il()

    ret = INF
    for k in range(K//L + 2):
        ret = min(ret, B * k + max(0, (K - (L * k)) * A))
    print(ret)


if __name__ == '__main__':
    main()

考え方

セットのミカンをいくつ買うか取りうる範囲を全探索し、
最も安く買える選択を回答とする。

---

L個セットをいくつ買うか決めると、残りの変数を一意に決めることができる。
具体的には、A=4, B=5, K=11, L=3のとき、
セットのミカンを１つも買わない場合、
全てのミカンを個別で購入する必要があるため、A * K = 44円。
セットのミカンを１つ買う場合、
セットのミカンがB * 1 = 5 * 1 = 5円で、残りはK - (L * 1) = 11 - (3 * 1) = 8個のミカンが必要となる。
そのため、個別のミカンがA * 8 = 4 * 8 = 32円で、合計37円。

あとは上記のような計算を、購入しうるセットのミカンの個数だけ計算して、最も安く買える金額を探索する。
欲しいミカンの数をセットのミカンで丁度購入することが出来ない場合、
個別のミカンは１つも買わなくてよいため、0円となる点にだけ注意。
（L - (K * 購入するセットの数)がマイナスとなりうることがある）