AGC 044 A – Pay to Win をPythonで解いた【動的計画法 メモ化再起 AtCoder Grand Contest 044】

競プロ

どうも,京大博士課程のざるご( @zalgo3 )です.

問題文(引用)

引用元:https://atcoder.jp/contests/agc044/tasks/agc044_a

あなたは 0 という数を持っており、これをN に変えようとしています。

あなたが持っている数は、以下の操作により、定まった枚数のコインを支払うことで変化させることができます。

  • A 枚のコインを支払い、持っている数を 2 倍する。
  • B 枚のコインを支払い、持っている数を 3 倍する。
  • C 枚のコインを支払い、持っている数を 5 倍する。
  • D 枚のコインを支払い、持っている数を1 増やす、または 1 減らす。

これらの操作は、任意の順に何度でも行うことができます。

持っている数を N とするには、最小で何枚のコインが必要でしょうか。

解答

コンテスト中なんもわからんで提出無しを決めましたが,解説を見て復習がてら実装してみました.

逆向きから始めると考えるのがポイントで,Nからはじめて割り算と,プラスマイナスを繰り返して0にする問題と考えます.

すると,全部マイナスで0までいくか,プラスマイナスを繰り返してから除算を行う操作からはじめるかのどちらかに必ずなります.

すると,nのときのコストをf(n)と表して,動的計画法で解くことができます.

この流れを,Pythonでメモ化再帰を使って実装してみた結果が以下です.

import sys
sys.setrecursionlimit(10**6)
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {0: 0, 1: d}
    def cost(N):
        if N in memo:
            return memo[N]
        ans = N * d
        ks = [2, 3, 5]
        abc = [a, b, c]
        for i in range(3):
            k = ks[i]
            coin = abc[i]
            div, mod = divmod(N, k)
            pay = mod * d + coin
            ans = min(ans, pay + cost(div))
            if mod == 0:
                continue
            pay = (k - mod) * d + coin
            ans = min(ans, pay + cost(div + 1))
        memo[N] = ans
        return ans
    print(cost(n))

コメント

タイトルとURLをコピーしました