Critique du concours AtCoder

Les résultats de cette fois

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.