[PYTHON] AtCoder Grand Contest 044 Review

Impressions of this time

A The problem was difficult (I couldn't analyze the amount of calculation), and when I was wondering how to implement it, the time was up. Maybe it's okay to pass it, so it might be a good idea to throw it. As a result, NoSub withdrew ... Also, I would like to solve the B problem in my spare time this week.

Problem A

First, I would like to mention the methods considered during the contest. I thought that +1 and -1 were for adjustment, and I thought that it might be uniquely determined by ** repeating one of 2 times, 3 times, and 5 times. Therefore, I thought that $ n $ should be considered as a $ k $ ($ \ in $ {$ 2,3,5 $}) base number, but of course it is not decided by referring to the sample (1 without noticing this) It melted for more than an hour. If you rush, you will not be able to think logically ...).

Anyway, if you can't solve it, take the courage to change your policy! !!

By the way, before sticking to this policy, I tried to think of DP ** which made a note of the number of coins required from ** $ n $ to 0, and decided that it was impossible because the number of DP elements is $ n $. It was. ** You can speed up DP by using a dictionary instead of an array of memos **, so you can solve it by this method (close to).

Now consider using $ n $ to +1, -1, ÷ 2, ÷ 3, ÷ 5 to make it 0. First, when you know the number of coins you need for a certain $ l $, use +1, -1, ÷ 2, ÷ 3, ÷ 5 to narrow down the number of destinations to move ** (** state) Limited ** is the basics such as DP). For example, suppose you want to do $ l $ ÷ 5. Since $ l $% 5 = 0 is required for this answer to be an integer, let $ l $ act +1, -1 to make it divisible by 5.

Here, if you apply +6 or more or -6 or less to $ l $, you will use coins of $ 6 \ times D $ or more at that point, but in this case, ** 6 or more or -6 or less. It is clear that it is more efficient to break the coin before breaking it than to let it work **. 11 → 10 → 1 ("-1" × 1 → "÷ 5" → "-1" × 1) is better than (eg 11 → 5 → 1 ("-1" × 6 → "÷ 5")) You'll spend fewer coins.) (You can probably prove it by doing something similar, but I'll omit it here.)

Similarly, if the number of coins required to make a certain l and the number to be divided $ k $ ($ \ in $ {$ 2,3,5 $}) are determined, the minimum number of coins will be obtained. In such an operation, move to a multiple of the number you want to divide (2,3,5) close to ** $ l $ ** (← Note that there are two, it is written as * nearest * in the code) Then divide and perform the next calculation. At this time, a recursive structure (fractal structure) appears, so recursion should be implemented, and memoized DFS (also considered as DP) should be implemented.

Also note that in some cases it is best to just do -1 and change from $ l $ to $ 0 $ without using division. (← Up to this point, if you want to aim for 0 with ** ÷ 2, ÷ 3, ÷ 5, you are only thinking about **, so if you want to aim for 0 with ** -1, you have to consider ** Of course.)

A.py

def dfs(n):
    global b,check,d
    #ttf is 235, cha is abc
    #2,3,In case of 5, each
    for ttf,cha in zip([2,3,5],b):
        #-When going one by one
        if check[0]>check[n]+n*d:
            check[0]=check[n]+n*d

        #To the nearest-If you do
        x1,x2=n//ttf,n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

        #To the nearest+When 1 comes
        x1,x2=n//ttf+1,ttf-n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])