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.)
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))
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")
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)
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)
Recommended Posts