[PYTHON] AtCoder Beginner Contest 093 Revue des questions précédentes

Temps requis

Impressions

D Le problème était difficile ... J'avais peur du problème en 700 points et il a fallu beaucoup de temps pour l'examiner. Ce n'est pas aussi difficile qu'il y paraît, alors j'aimerais avoir une solide conscience de ** verbaliser le processus **.

Problème A

Trier et combiner → Puisque les caractères inclus dans la chaîne de caractères sont les mêmes, ici il s'agit uniquement de a, b, c, il est donc jugé si la longueur de l'ensemble est de 3.

answerA.py

s=input()
print("Yes" if len(set(s))==3 else "No")

Problème B

Si vous suivez de a à b dans l'ordre, le maximum est $ 2 \ times10 ^ 9 $, donc a → a + k-1 et b-k + 1 → b sont affichés séparément.

answerB.py

a,b,k=map(int,input().split())
if (b-a+1)>=2*k:
    for i in range(a,a+k):
        print(i)
    for i in range(b-k+1,b+1):
        print(i)
else:
    for i in range(a,b+1):
        print(i)

Problème C

L'opération de sélection d'un nombre et son augmentation de deux et l'opération de sélection de deux nombres et son augmentation de un ont le même effet sur le total total **. Aussi, dans le cas de l'opération d'augmentation de 1, la ** relation paire-impaire entre les deux nombres sélectionnés et celui non sélectionné change **, et dans le cas de l'opération d'augmentation de deux, celui sélectionné et les deux nombres non sélectionnés Cela signifie que la ** relation paire-impaire entre les nombres ne change pas **. En d'autres termes, si la régularité et la bizarrerie des trois nombres sont égales au début, seule l'opération d'augmentation de 2 est effectuée pour augmenter le nombre jusqu'au nombre maximum. Vous pouvez égaliser les paires et les impairs des trois nombres en sélectionnant et en augmentant de un. En outre, le premier est le code écrit pendant le test, et le second est le code raccourci à l'aide de l'opérateur XOR. De plus, comme vous pouvez le voir dans la Réponse, si vous suivez la solution Writer, vous pouvez écrire un code encore plus court.

answerC.py

a,b,c=map(int,input().split())
if a%2==b%2 and b%2==c%2:
    x=sorted([a,b,c])
    print((x[2]-x[1])//2+(x[2]-x[0])//2)
elif a%2==b%2:
    a+=1
    b+=1
    x=sorted([a,b,c])
    print((x[2]-x[1])//2+(x[2]-x[0])//2+1)
elif b%2==c%2:
    b+=1
    c+=1
    x=sorted([a,b,c])
    print((x[2]-x[1])//2+(x[2]-x[0])//2+1)
else:
    c+=1
    a+=1
    x=sorted([a,b,c])
    print((x[2]-x[1])//2+(x[2]-x[0])//2+1)

answerC_shorter.py

a,b,c=map(int,input().split())
p=(a%2!=b%2)or(b%2!=c%2)
a,b,c=sorted([a+((a%2==b%2)^(a%2==c%2)),b+((b%2==a%2)^(b%2==c%2)),c+((c%2==a%2)^(c%2==b%2))])
print((c-a)//2+(c-b)//2+p)

Problème D

J'avais peur quand je l'ai vu pour la première fois ... La réponse a été écrite dans un style génial, il m'a donc fallu un certain temps pour la comprendre, mais [le blog de Kenchon](https://drken1215.hatenablog.com/entry/2018/09/08/ J'ai pu formuler ma propre façon de penser en me référant à 195000) et au blog de kmjp. (C'est difficile, mais en poursuivant ma réflexion, j'ai réalisé que c'était un très bon problème.)

Tout d'abord, nous allons procéder à la discussion basée sur cette hypothèse car $ A \ leqq B $ ne perd pas sa généralité. Ici, ** si la personne de la 1ère à la 1ère place dans la première fois prend la B + A-1 à B + 1ère place dans la seconde fois, , le produit est AB à partir de la condition $ A \ leqq B $. Ce sera plus petit. De même, si les personnes du premier à A-1 prennent la place B + A-1 à B + 1 chacune la deuxième fois, ces personnes auront également un produit inférieur à $ A \ fois B $. Par conséquent, on peut voir que la solution à rechercher est 2A-2 ou plus ** ( rétrécissez autant que possible la plage à rechercher !! **). À partir de là, vous devez considérer ** combien de personnes parmi les premières A + 1 ~ B et les secondes A ~ B-1 auront un score inférieur à AB **. Premièrement, quand A = B, il n'y a pas de telle personne, et quand A = B-1, la première fois est A + 1 et la deuxième fois est B-1 donc le score est AB + (BA) + 1> Puisqu'il s'agit de AB, le score ne sera pas inférieur à AB (excluez ces deux fermement **). De ce qui précède, nous considérerons sous B> A + 1. Ici, supposons que la personne dans la position A + 1 à A + x dans la première fois prenne la position A + x-1 à A dans la deuxième fois, respectivement. La valeur maximale du produit à ce moment est $ (2A + x) // 2 \ times ((2A + x) - (2A + x) // 2) $ (✳︎1). Par conséquent, pour $ 1 \ leqq x \ leqq BA $, $ (2A + x) // 2 \ times ((2A + x) - (2A + x) // 2) $ est inférieur à AB ** Maximum x Vous pouvez trouver **, et un tel x peut être trouvé par ** dichotomie **. De ce qui précède, faites attention à A <= B pour la réponse que vous recherchez. 2A-2 lorsque A = B ou A = B-1 Lorsque A <B-1, 2A-2 + x (1 <= x <= B-A) (✳︎2)

(✳︎1)… $ x \ times y $ (x + y = k) (x, y, k sont tous des entiers positifs) prend la valeur maximale (x, y) = (k // 2, kk Ce sera au moment de // 2). Ceci est clair si vous éliminez x ou y et considérez le maximum et le minimum ou la symétrie de x et y.

(✳︎2)… Ici, lorsque x est 1 de B> A + 1, la première fois est A + 1 et la deuxième fois est A, donc A (A + 1) <AB est valable pour le score. Par conséquent, on peut dire que x> = 1.

(✳︎3)… Lorsque «chacun» est écrit ci-dessus, cela signifie combiner dans l'ordre inverse. De plus, à ce moment-là, il est écrit qu'il sera plus petit que AB, mais veuillez calculer et vérifier vous-même s'il est plus petit que AB. De plus, en recherchant avant et après la combinaison qui devient ** AB, vous pouvez trouver une combinaison plus petite que la dernière minute **. (Je ne pouvais pas le faire pendant Bachacon, mais en regardant les articles d'autres personnes, j'ai senti que c'était une idée naturelle.)

answerD.py

q=int(input())
def check(t,a,b):
    k=(2*a+t)//2
    return k*(2*a+t-k)<a*b

for i in range(q):
    a,b=sorted(map(int,input().split()))
    if a==b or a==b-1:
        print(2*a-2)
        continue
    l,r=1,b-a
    while l+1<r:
        t=(l+r)//2
        if check(t,a,b):
            l=t
        else:
            r=t
    if check(r,a,b):
        print(2*a-2+r)
    elif check(l,a,b):
        print(2*a-2+l)
    else:
        print(2*a-1)