[PYTHON] Critique du concours AtCoder

Les résultats de cette fois

スクリーンショット 2020-08-07 17.46.27.png

Impressions de cette époque

J'ai fait une erreur de ne pas pouvoir résoudre le problème C. Le sujet n'a pas pu être lu avec précision. ** Si vous avez un problème, vérifiez le mouvement avec un échantillon **.

Il semble que de nombreuses personnes ont étudié et résolu le problème F. Je pense que c'est un problème intéressant, mais je savais comment le résoudre, alors j'essaierai de le résoudre quand je l'oublierai. ** Il y a pas mal de problèmes qui permettent d'en trouver un facilement dans la section **, mais c'est facile à oublier, donc je veux m'assurer de pouvoir le résoudre la prochaine fois.

Problème A

Il vous suffit de vérifier s'il fait plus de 30 degrés.

A.py


print("Yes" if int(input())>=30 else "No")

Problème B

Trouvez juste la distance. De plus, cette fois, je crains que l'itinéraire ne soit une fraction, alors je l'ai mis au carré (il semble qu'il soit correct de calculer l'itinéraire tel qu'il est dans ce problème).

B.py


n,d=map(int,input().split())
ans=0
for i in range(n):
    x,y=map(int,input().split())
    ans+=(x**2+y**2<=d**2)
print(ans)

Problème C

Un multiple de ** $ K $ peut être reformulé comme 0 ** avec le reste divisé par $ K $. Aussi, si le $ i $ th de $ 7,77,777,… $ est $ a_i $, alors $ a_ {i + 1} = 10 \ fois a_i + 7 $. Par conséquent, si les restes de $ a_j et a_l $ sont les mêmes, les restes de $ a_ {j + 1} et a_ {l + 1} $ seront également les mêmes. Par conséquent, il y a quelque chose qui souffre du reste divisé par ** $ K $ jusqu'à $ a_ {K + 1} $ **, donc si vous recherchez $ a_1 $ ~ $ a_k $, le reste divisé par $ K $ sera Vous pouvez rechercher des 0. Par contre, si 0 ne sort pas jusque-là, il n'y a rien pour que le reste après la division par $ K $ devienne 0.

Dans ce problème, vous pouvez résoudre le problème en faisant attention au reste de ** $ K $ si vous remarquez que le reste de ** $ K $ divisé par $ K $ est de 0 **. De plus, comme il est inclus dans les bases de la ** simulation pour le moment lors de la résolution d'un problème **, je me suis rendu compte à nouveau de l'importance de bien mettre en œuvre les bases.

C.py


k=int(input())
now=7%k
if now==0:
    print(1)
    exit()
for i in range(1,k):
    now=10*now+7
    now%=k
    if now==0:
        print(i+1)
        break
else:
    print(-1)

Problème D

Il est facile de voir que la séquence finale est "rouge-rouge ... rouge-rouge / blanc-blanc ... blanc-blanc". Tout d'abord, pour ** changer avidement la rangée de pierres donnée **, nous la changerons de gauche en rouge.

Pour le moment, il n'est pas nécessaire de changer Akaishi, alors considérez ** uniquement pour Shiraishi **. En ce moment, je pense changer la pierre blanche en pierre rouge, mais si vous la remplacez par la pierre rouge sur le côté droit de la pierre plutôt que de recolorer la pierre, vous pouvez changer la couleur de deux pierres en même temps **, donc c'est efficace. est. De plus, vous pouvez voir que ** remplacer par la pierre rouge la plus à droite ** est approprié pour remplacer par une pierre rouge afin de réduire le nombre de remplacements (← Par exemple, ** Cas extrême ** (à côté de). Je pense que c'est facile à comprendre vu qu'il est inefficace (en le remplaçant par Akaishi). Si vous pouvez créer une situation où il n'y a pas de pierre rouge sur le côté droit tout en répétant cela, le nombre d'opérations à ce moment-là sera le nombre minimum d'opérations.

D.py


from collections import deque
n=int(input())
c=input()
r=deque()
lr=0
for i in range(n):
    if c[i]=="R":
        lr+=1
        r.append(i)
ans=0
for i in range(n):
    if lr==0:
        break
    if c[i]=="W":
        if i<r[-1]:
            ans+=1
            r.pop()
            lr-=1
        else:
            break

print(ans)

E problème

Vous pouvez penser à une dichotomie en combinant le nombre de fois qu'une bûche est coupée (le nombre de fois), le minimum (avec une large gamme de nombres), et ** plus la bûche est longue, moins elle est coupée ** (monotonie).

Ici, ** dans la dichotomie, il faut considérer la condition qui vaut toujours pour le minimum (ou maximum) ou plus **, mais ici, "au moins nécessaire pour rendre la plus longue longueur (arrondie) inférieure à $ x $". La condition est que le nombre de fois qu'un journal est coupé est de $ K $ ou moins, et le total de ceil (a [i] / x) -1 calculé pour chaque journal est de $ K $ ou moins. Si c'est bon.

Notez également que pour l, r, ** $ l $ est toujours défini sur une valeur qui ne tient pas toujours **, ** $ r $ est défini sur une valeur qui ne tient pas toujours **.

Si vous y prêtez attention, vous pouvez trouver la bonne réponse en implémentant selon cet article.

E.py


n,k=map(int,input().split())
a=list(map(int,input().split()))
def f(x):
    global a,n,k
    if x==0:
        return 10**10
    ret=0
    for i in range(n):
        ret+=(-((-a[i])//x)-1)
    return ret

l,r=0,10**10
while l+1<r:
    x=l+(r-l)//2
    if f(x)<=k:
        r=x
    else:
        l=x

print(r)

F problem

Je ne résoudrai pas cette fois.

Recommended Posts

Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
Critique du concours AtCoder
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
Concours AtCoder Débutant 181 Remarque
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Concours AtCoder Débutant 180 Remarque
AtCoder Grand Contest 048 Critique
Concours AtCoder pour débutants 156 WriteUp
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Concours AtCoder pour débutants 167
Concours AtCoder Débutant 183 Remarque
AtCoder Regular Contest 106 Évaluation
Concours AtCoder Débutant 184 Remarque
AtCoder Grand Contest 046 Critique
Revue du concours régulier AtCoder 104
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