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

Temps requis

スクリーンショット 2020-04-09 13.31.30.png

Impressions

Dans le passé, je ne pouvais pas résoudre le problème XOR, mais une fois que j'ai appris les bases qu'il serait plus facile de calculer en divisant chaque chiffre en binaire, je pouvais le résoudre. L'explication et le code de D sont difficiles à comprendre, j'attends donc des suggestions d'amélioration.

Problème A

Trouvez simplement max.

answerA.py


a,b=map(int,input().split())
print(max(a+b,a-b,a*b))

Problème B

Il existe N-1 façons de se diviser en x et y, et en faisant de x et y un ensemble au lieu d'une chaîne pour chacun, la taille du plus grand ensemble de produits est la réponse.

answerB.py


n=int(input())
s=input()
ans=0
for i in range(n-1):
    s1=s[:i+1]
    s2=s[i+1:]
    s3=set(s1)&set(s2)
    ans=max(ans,len(s3))
print(ans)

Problème C

Au moment de choisir un chef, vous pouvez compter le nombre de personnes à l'ouest de ce chef qui font face à l'ouest et celles qui sont à l'est de ce chef qui font face à l'est, mais le nombre de personnes est O ( Doit être calculé par 1) ou O (log (n)). Ici, puisque le nombre de personnes est ** somme cumulative **, il peut être calculé par O (1) en calculant le nombre de personnes faisant face à l'ouest et celles faisant face à l'est comme somme cumulée.

answerC.py


n=int(input())
s=input()
l=[0]*n
r=[0]*n
for i in range(1,n):
    l[i]=l[i-1]+(s[i-1]=="W")
for i in range(n-2,-1,-1):
    r[i]=r[i+1]+(s[i+1]=="E")
ans=n-1
for i in range(n):
    ans=min(ans,l[i]+r[i])
print(ans)

Problème D

Tout d'abord, j'ai pensé à paraphraser parce que xor devient égal à +. Ensuite, dans XOR, j'ai remarqué qu'il n'y a pas de report ** car le nombre de 1 dans chaque chiffre est 1 lorsqu'il s'agit d'un nombre impair et 0 lorsqu'il est pair lorsqu'il est converti en nombre binaire. Par conséquent, lors de l'ajout, vous pouvez voir que ** s'il n'y a pas de report pour tous les chiffres **, le sujet est satisfait. De plus, en d'autres termes, il n'y a pas de report dans le i-ième chiffre **, ce qui équivaut au nombre de $ A_l… A_r $ où le i-ième chiffre est 1 ou moins **. Je vais. À partir de ce qui précède, préparez d'abord un tableau qui stocke le nombre de 1 dans chaque chiffre. Sur cette base, nous rechercherons des candidats pour l et r, mais en considérant si $ A_l… A_ {r + 1} $ tient quand $ A_l… A_r $ tient, $ A_l… A_r $ et $ A_l… A_ { Lorsque vous faites attention à chaque chiffre de r + 1} $, le nombre de ** 1 est soit augmenté soit inchangé **. Par conséquent, lorsque l est fixé, l'ensemble de (l, r) qui ne dépasse pas 2 compte tenu du nombre de 1 dans chaque chiffre de $ A_l… A_r $ pour r = l + k (k> = 1) est le sujet. Rencontrer. De plus, si vous utilisez la ** méthode de mise à l'échelle ** à ce stade, vous pouvez compter tous les candidats (l, r) en déplaçant ** r pour satisfaire le thème, puis en déplaçant l **. Je vais. Comme j'ai oublié comment implémenter la méthode scale, je vais revoir le code de la méthode scale, mais pour plus de détails, reportez-vous à l'article de Kenchon S'il vous plaît. La chose importante à propos de ce problème est que lorsque ** (l, r) tient, (l + 1, r) tient également ** (comme vous pouvez le voir dans la discussion jusqu'à présent). Par conséquent, lors de la prise de l'échelle, lorsque l est fixe et r est augmenté tout en satisfaisant le sujet, ** (l + 1, r) vaut également pour tout r **. Par conséquent, il est possible de tourner efficacement l en tournant 0 → n-1 en tournant l'instruction for, et en maintenant et en augmentant r séparément de l'instruction for. À propos, Python n'a pas réussi même avec cette méthode d'échelle, alors je l'ai passé avec PyPy.

L'explication est difficile à comprendre et le code est un peu difficile à comprendre, alors faites-le moi savoir si vous avez des suggestions d'amélioration.

Post-scriptum (11/04/2020)

Considérant le cas où il n'y a pas de report pour tous les chiffres, les résultats de l'opération + et de l'opération ^ seront les mêmes, donc en sauvegardant respectivement les résultats de l'opération + et de l'opération ^, "pour chaque chiffre" Il peut être utilisé comme alternative à un tableau qui stocke le nombre de 1 (de cette façon, vous pouvez également utiliser Python, voir les commentaires pour plus d'informations). De plus, le deuxième code est implémenté de cette manière.

answerD.py


n=int(input())
a=list(map(int,input().split()))
ans=0
right=0
now=[0]*20#2^Parce que c'est 20
for i in range(n):
    left=i
    if i!=0:
        for j in range(20):
            if (a[left-1]>>j)&1:
                now[j]-=1
    else:
        for j in range(20):
            if (a[left]>>j)&1:
                now[j]+=1
    while all([now[j]<=1 for j in range(20)]):
        right+=1
        if right==n:
            break
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]+=1
    else:
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]-=1
    right-=1
    ans+=(right-left+1)
print(ans)

answerD2.py


n=int(input())
a=list(map(int,input().split()))
ans=0
right=0
np,nx=a[0],a[0]
for left in range(n):
    while np==nx:
        right+=1
        if right==n:
            break
        np+=a[right]
        nx^=a[right]
    else:
        np-=a[right]
        nx^=a[right]
    right-=1
    ans+=(right-left+1)
    np-=a[left]
    nx^=a[left]
print(ans)

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 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 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 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 053 Revue des questions précédentes
AtCoder Beginner Contest 094 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 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
AtCoder Beginner Contest 125 Revue des questions précédentes
AtCoder Beginner Contest 109 Revue des questions précédentes
AtCoder Beginner Contest 118 Revue des questions précédentes