AtCoder Beginner Contest 044 Revue des questions précédentes

Temps requis

スクリーンショット 2020-02-01 15.13.49.png

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)

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes