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

Temps requis

スクリーンショット 2020-05-16 13.48.21.png

Impressions

Je n'ai pas pu le terminer avant la fin à cause de quelques courses, mais je pense que c'était un ensemble qui pourrait être terminé rapidement même si je n'avais pas le temps si j'étais calme. Ce serait bien de pouvoir le retirer fermement lors de l'utilisation d'un tel ensemble.

Problème A

Si vous réduisez la différence dans le nombre de galettes de riz, la différence sera d'au plus un (je ne le prouverai pas, mais je pense que c'est évident). Par conséquent, considérons le cas où la différence est 0, mais dans ce cas n est divisible par k. S'il s'agit d'une sortie, ce sera comme suit.

answerA.py


n,k=map(int,input().split())
print(1 if n%k!=0 else 0)

Problème B

Recherchez des combinaisons possibles où n n'est pas grand. En supposant combien de beignets à 7 $ vous avez achetés, vous pouvez acheter un gâteau à 4 $ avec le reste de l'argent.

answerB.py


n=int(input())
for i in range(n//7+1):
    if (n-i*7)%4==0:
        print("Yes")
        break
else:
    print("No")

Problème C

Je n'aurais pas dû voir le problème et avoir l'impression que je devais le faire correctement. Je veux me souvenir des bases de ** réfléchir attentivement puis de résoudre **. Dans la réponse, je le résolve en utilisant ** qui est uniquement déterminé en décidant à partir du chiffre inférieur ** (je n'ai pas remarqué du tout ...), mais je ** à l'inverse décide à partir du chiffre supérieur et le résout. C'était **.

Au moment de décider à partir des chiffres supérieurs, j'ai remarqué que la plage de nombres pouvant être représentée se rétrécit. C'est,|S_0 \times (-2)^0+S_1 \times (-2)^1+…+S_{k-1} \times (-2)^{k-1}|<|S_k \times (-2)^k|Est vrai.

Sauf pour les modèles où cela ne tient pas, la réponse est que lorsque vous décidez à partir des chiffres supérieurs et ajoutez chaque chiffre, il finira par devenir égal à n, donc inversement soustrayez chaque chiffre de n pour le rendre 0. J'y ai pensé.

En faisant cela, la valeur absolue lorsque le kème chiffre est décidé|S_k \times (-2)^k|Le modèle doit être celui qui exclut les cas ci-dessus.

Il y a plusieurs candidats, donc ** vous pouvez enregistrer les candidats lorsque vous avez décidé jusqu'à un certain chiffre avec deque et recherchez la réponse avec BFS **.

De plus, à ce stade, le montant spécifique du calcul est gênant, je ne l'ai donc pas calculé, mais comme il peut être clairement omis par l'élagage, je l'ai mis en œuvre sans le calculer.

answerC.py


from itertools import dropwhile
from collections import deque
n=int(input())
ans=deque([["",n]])
def bfs(d):
    global ans
    l=len(ans)
    for i in range(l):
        x=ans.popleft()
        new1=[x[0]+"0",x[1]]
        if abs(new1[1])<abs((-2)**d):
            ans.append(new1)
        new2=[x[0]+"1",x[1]-(-2)**d]
        if abs(new2[1])<abs((-2)**d):
            ans.append(new2)
    if d!=0:
        bfs(d-1)
bfs(32)

for i in ans:
    if i[1]==0:
        ans=list(dropwhile(lambda x:x=="0",i[0]))
        if len(ans)==0:
            print(0)
        else:
            print("".join(ans))
        break

Problème D

Je pense que c'est un problème similaire au problème qui s'est posé à ABC l'autre jour (j'ai oublié lequel).

Puisqu'on vous demande si la ** partie continue ** est un multiple de M, il semble que vous devriez vous demander si la soustraction de la somme cumulée est un multiple de M ** (** Si vous calculez l'intervalle plusieurs fois) Est la somme cumulée, si ce n'est pas possible, BIT ou Seg tree **). Autrement dit, lorsque (l, r) est donné comme un ensemble, $ S [l, m] = A_l + A_ {l + 1} +… + A_m $, et $ S [l, m] = S [1, m ] -S [1, l-1] \ (1 \ leqq l \ leqq r \ leqq N ) Considérons le nombre total de paires de (l, m) qui contiennent $. De plus, si $ S [1,0] = 0 $, alors $ S [l, m] = S [1, m] -S [1, l] \ (0 \ leqq l <r \ leqq N ) Vous pouvez penser au nombre total de paires qui valent $.

Autrement dit, considérons $ S [1, k] % m $ avec k = 0 à N, enregistrez le nombre de sommes cumulées (x) sont les restes (en utilisant Counter) et utilisez chaque reste. Tout ce que vous avez à faire est de calculer $ _x C _2 $ et d'utiliser la somme comme réponse.

answerD.py


from itertools import accumulate
from collections import Counter
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,m=map(int,input().split())
s=list(map(lambda x:x%m,list(accumulate(list(map(int,input().split()))))))
s.append(0)
d=Counter(s)
ans=0
for i in d:
    if d[i]>=2:
        ans+=combinations_count(d[i],2)
print(ans)

answerD_shortest.py


n,m,*c=map(int,open(0).read().split());d={0:1};r=s=0
for i in c:s+=i;x=d.get(s%m,0);r+=x;d[s%m]=x+1
print(r)

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 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 127 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 067 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 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 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 126 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 059 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