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

Temps requis

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)