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

Temps requis

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

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)

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 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 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 105 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 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 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 121 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 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 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 063 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 058 Revue des questions précédentes
AtCoder Beginner Contest 043 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