[PYTHON] AtCoder Beginner Contest 044 Revue des questions précédentes

Temps requis

Impressions

D Le problème était serré ... J'ai fait beaucoup d'erreurs parce que je n'ai pas fait beaucoup de ce type de DP pour le problème C, donc je dois couvrir correctement le DP ... Je semblais être capable de passer le problème D avec une solution adaptée au mensonge, mais ce n'est pas du tout bon, alors j'ai lu la réponse ... (Il est décevant qu'il ne semble pas être à pleines dents quand il devient jaune. Après tout, j'ai senti que ce problème pouvait être résolu en l'examinant.)

Problème A

Va-t-il dépasser ou ne pas dépasser 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))

Problème B

Si vous triez et regroupez par groupe, vous pouvez savoir combien il y en a. S'il y a un nombre impair, la sortie No.

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

Problème C

J'ai l'impression que le problème C était un peu difficile cette fois. La moyenne devrait être A, mais après tout, quand il y a n feuilles, le total sera n * A. Aussi, j'ai pensé à DP ** car il est difficile de penser goulûment à un tel cas et j'ai besoin de bien choisir une carte (j'ai l'impression que la plupart des modèles pour DP sont bien choisis dans les limites). .. Cependant, bien qu'il ne s'agisse que d'un DP, je suis assez confus car je pense généralement au min et au max. Tout d'abord, enregistrez ** dp [j] [k] combien de cas l'entier j peut être représenté par k cartes ** (dp [0] [0] est facile à calculer plus tard) Laissez-le à 1.). De plus, en considérant l'entier $ x_i $ dans dp [j] [k], lorsque dp [j] [k] = 0, l'entier j ne peut pas être représenté par k cartes à ce stade, alors mettez-le à jour. Cependant, lorsque dp [j] [k] $ \ ne0 $, mettez à jour comme `dp_sub [j + x [i]] [k + 1] = dp [j] [k]` `( Puisqu'il n'y a qu'une carte à la fois, vous devez préparer dp_sub.) Ensuite, en reflétant (+) ce que vous avez écrit dans dp_sub dans dp, la mise à jour est terminée, et vous pouvez penser à cela comme i: 1 → n. Enfin, la réponse est obtenue en ajoutant les éléments ( dp [a * (i + 1)] [i + 1] ``) où la moyenne des entiers de dp est exactement 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)

Problème D

Hmmm, la réponse n'est-elle pas trop géniale, peu importe combien de fois vous la regardez? Ci-dessous, je vais organiser dans mes propres mots en fonction de cette réponse.

Premièrement, si vous pensez au temps de ** n \ <s **, f (b, n) sera toujours inférieur ou égal à b (je ne l'ai pas prouvé, mais je ne pense pas que ce soit si difficile). Il n'y a pas de b qui satisfait f (b, n) = s (sorties -1). Ensuite, considérons le temps de ** n = s **, b \ <= n est f (b, n) \ <s et b > = n + 1 est (b, n) = s, donc b Il est facile de voir que = n + 1 est le plus petit. Ci-dessous, nous allons procéder à la discussion comme ** n > s **.

Tout d'abord, c'est $ n \ leqq 10 ^ {11} $, mais comme il n'est pas monotone et que la dichotomie ne peut pas être utilisée, il peut être possible de le passer avec ** $ O (\ sqrt {n}) $, ce qui semble être le prochain petit calcul. Je soupçonne que ce n'est pas ** (j'ai remarqué ceci, c'est une image ** qui se réduit à la plage accessible avec le montant de calcul de ** $ O (\ sqrt {n}) $). Pour le moment, b: 2 → $ \ sqrt {n} $ pour trouver le plus petit b pour lequel $ f (b, n) = s $, et s'il n'est pas trouvé, $ \ sqrt {n} <b \ leqq n $ pour le plus petit Supposons que vous recherchiez b. Ensuite, $ \ sqrt {n} <b \ leqq n $, donc si vous remarquez que ** n est toujours à 2 chiffres ** quand vous pensez en b-aire, $ 1 \ leqq p <b $, $ 0 \ leqq q Il peut être exprimé comme <b $ par $ n = pb + q $… (1). De plus, $ p + q = s $… (2) peut être dit à partir du sujet.

De plus, à partir de (1), $ n = pb + q> pb> p ^ 2 $, donc $ 1 \ leqq p <\ sqrt {n} $ peut être dit (car b est également décidé si p ou q est décidé. ** Motivation pour réduire la plage de p et q **.) Par conséquent, le candidat pour p est trouvé par $ O (\ sqrt {n}) $, et b est uniquement déterminé comme $ b = (ns) / p + 1 $ à partir des équations (1) et (2). La solution peut être trouvée en recherchant le plus petit b tel que $ f (b, n) = s $.

Ce qui précède est mis en œuvre et devient comme suit. (Il m'a fallu une heure et demie pour déboguer, oubliant le = dans la partie du code qui dit `` ici ''. Je suis sur le point de mourir.)

answerD.py

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

def f(b,n):
    m=math.floor(n/b)
    if n>=b:#ici
        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)