[PYTHON] AtCoder Beginner Contest 044 Review of past questions

Time required

Impressions

D The problem was tight ... I made a lot of mistakes because I didn't do much of this type of DP for the C problem, so it is necessary to cover the DP properly ... D problem, I seemed to be able to pass the lie with an appropriate solution, but it is not good at all, so I will read the answer ... (It's disappointing that it doesn't seem to be toothy when it turns yellow. After all, I felt that this problem could be solved by reviewing it.)

Problem A

Will it exceed or not exceed k?

answerA.py

n=int(input())
k=int(input())
x=int(input())
y=int(input())
print(x*n if n<=k else x*k+y*(n-k))

B problem

You can find out how many are there by sorting and group-by. If there is an odd number, No is output.

answerB.py

def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2
w=list(input())
w.sort()
w=groupby(w)
for i in w:
    if i[1]%2==1:
        print("No")
        break
else:
    print("Yes")

C problem

I feel that the C problem was a little difficult this time. The average should be A, but after all, when there are n sheets, the total will be n * A. Also, I thought about DP ** because it is difficult to greedily think about such a case and I need to choose a card well (I feel that most DPs have a pattern to choose well within the limits). .. However, although it is just a DP, I am quite confused because I usually think about min and max. First, record ** dp [j] [k] how many cases the integer j can be represented by k cards ** (dp [0] [0] is easy to calculate later) Leave it at 1.). Also, when considering the integer $ x_i $ in dp [j] [k], when dp [j] [k] = 0, the integer j cannot be represented by k cards at that point, so update it. However, when dp [j] [k] $ \ ne0 $, update as `dp_sub [j + x [i]] [k + 1] = dp [j] [k]` ( Since there is one card at a time, you need to prepare dp_sub.) Then, the update is completed by reflecting (+) what you wrote down in dp_sub in dp, and you can think of this as i: 1 → n. Finally, the answer is obtained by adding the elements (dp [a * (i + 1)] [i + 1] `) where the average of the integers of dp is exactly a.

answerC.py

n,a=map(int,input().split())
x=list(map(int,input().split()))
x.sort(reverse=True)
sx=sum(x)
dp=[[0]*(n+1) for i in range(sx+1)]
dp[0][0]=1
for i in range(n):
    dp_sub=[[0]*(n+1) for j in range(sx+1)]
    for j in range(sx+1):
        for k in range(n+1):
            if dp[j][k]!=0:
                dp_sub[j+x[i]][k+1]=dp[j][k]
    for j in range(sx+1):
        for k in range(n+1):
            dp[j][k]+=dp_sub[j][k]
cnt=0

for i in range(min(sx//a,n)):
    cnt+=dp[a*(i+1)][i+1]
print(cnt)

D problem

Hmmm, isn't the answer too genius no matter how many times you look at it? Below, I will organize in my own words according to this answer.

First, if you think about the time of ** n \ <s **, f (b, n) will always be less than or equal to b (I haven't proved it, but I don't think it's that difficult). There is no b that satisfies f (b, n) = s (outputs -1). Next, consider the time of ** n = s **, b \ <= n is f (b, n) \ <s and b > = n + 1 is (b, n) = s, so b It's easy to see that = n + 1 is the smallest. Below, we will proceed with the discussion as ** n > s **.

First, it is $ n \ leqq 10 ^ {11} $, but since it is not monotonic and binary search cannot be used, it may be possible to pass it with ** $ O (\ sqrt {n}) $, which seems to be the next small amount of calculation. I suspect it is not ** (I noticed this, it is an image ** that narrows down to the accessible range with the computational complexity of ** $ O (\ sqrt {n}) $). For the time being, b: 2 → $ \ sqrt {n} $ to find the smallest b for which $ f (b, n) = s $, and if not found, $ \ sqrt {n} <b \ leqq n $ for the smallest Suppose you are looking for b. Then, $ \ sqrt {n} <b \ leqq n $, so if you notice that ** n is always 2 digits ** when you think in b-ary, $ 1 \ leqq p <b $, $ 0 \ leqq q It can be expressed as <b $ by $ n = pb + q $… (1). Furthermore, $ p + q = s $… (2) can be said from the subject.

Also, from (1), $ n = pb + q> pb> p ^ 2 $, so $ 1 \ leqq p <\ sqrt {n} $ can be said (because b is also decided if either p or q is decided. ** Motivation to narrow the range of p and q **.). Therefore, the candidate for p is found by $ O (\ sqrt {n}) $, and b is uniquely determined as $ b = (ns) / p + 1 $ from equations (1) and (2). The solution can be found by searching for the smallest b such that $ f (b, n) = s $.

Implementing the above, it becomes as follows. (It took me an hour and a half to debug, forgetting the = in the part of the code that says ``` here . I'm about to die.)

answerD.py

import math
n=int(input())
s=int(input())

def f(b,n):
    m=math.floor(n/b)
    if n>=b:#here
        return f(b,m) + n%b
    else:
        return n

if n<s:
    print(-1)
elif n==s:
    print(n+1)
else:
    for i in range(2,int(math.sqrt(n))+1):
        if f(i,n)==s:
            print(i)
            break
    else:
        for p in range(int(math.sqrt(n)),0,-1):
            if (n-s)%p==0:
                b=(n-s)//p+1
                if f(b,n)==s:
                    print(b)
                    break
        else:
            print(-1)