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])

Recommended Posts

AtCoder Grand Contest 041 Review
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 152 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Grand Contest 040 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Past Question Challenge 1
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 177
yukicoder contest 259 Review
yukicoder contest 264 Review
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
yukicoder contest 261 Review
AtCoder Beginner Contest 173
yukicoder contest 266 Review
Atcoder Beginner Contest 153
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions