[PYTHON] AtCoder Beginner Contest 093 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

D Das Problem war schwierig ... Ich hatte Angst vor dem 700-Punkte-Problem und es dauerte lange, es zu überprüfen. Es ist nicht so schwierig, wie es sich anhört, daher möchte ich ein solides Bewusstsein dafür haben, den Prozess zu verbalisieren.

Problem A

Sortieren und kombinieren → Die in der Zeichenfolge enthaltenen Zeichen sind gleich, daher besteht sie hier nur aus a, b und c, sodass beurteilt wird, ob die Länge des Satzes 3 beträgt.

answerA.py

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

B-Problem

Wenn Sie der Reihe nach von a nach b folgen, beträgt das Maximum $ 2 \ times10 ^ 9 $, sodass a → a + k-1 und b-k + 1 → b separat ausgegeben werden.

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)

C-Problem

Die Operation, eine Zahl auszuwählen und um zwei zu erhöhen, und die Operation, zwei Zahlen auszuwählen und um eins zu erhöhen, haben den gleichen Effekt auf die Gesamtsumme **. Außerdem ändert sich im Fall der Erhöhung um 1 die ** gerade-ungerade Beziehung zwischen den beiden ausgewählten Zahlen und der nicht ausgewählten ** und im Fall der Erhöhung um zwei die ausgewählte und die beiden nicht ausgewählten Zahlen Dies bedeutet, dass sich die ** gerade-ungerade Beziehung zwischen Zahlen nicht ändert **. Mit anderen Worten, wenn die Gleichmäßigkeit und Seltsamkeit der drei Zahlen zu Beginn gleich sind, sollte nur die Operation des Erhöhens um 2 durchgeführt werden, um auf die maximale Zahl zu erhöhen, und wenn die Gleichmäßigkeit und Seltsamkeit der drei Zahlen nicht gleich sind, sind die beiden gleich und eine ist unterschiedlich. Sie können die Gerade und Ungerade der drei Zahlen ausgleichen, indem Sie sie auswählen und um eins erhöhen. Ersteres ist der Code, der während des Tests geschrieben wurde, und letzteres ist der Code, der mit dem XOR-Operator gekürzt wurde. Wie Sie aus der Antwort ersehen können, können Sie, wenn Sie der Writer-Lösung folgen, noch kürzeren Code schreiben.

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)

D Problem

Ich hatte Angst, als ich es zum ersten Mal sah ... Die Antwort wurde in einem genialen Stil geschrieben, daher habe ich eine Weile gebraucht, um sie zu verstehen, aber [Kenchons Blog](https://drken1215.hatenablog.com/entry/2018/09/08/ Ich konnte meine eigene Denkweise unter Bezugnahme auf 195000 formulieren) und kmjps Blog. (Es ist schwierig, aber als ich mit meiner Überlegung fortfuhr, stellte ich fest, dass es ein sehr gutes Problem war.)

Zunächst werden wir mit der Diskussion fortfahren, die auf dieser Annahme basiert, da $ A \ leqq B $ seine Allgemeinheit nicht verliert. Hier ** ist das Produkt AB aus dem Zustand von $ A \ leqq B $, wenn die Person auf dem 1. bis A-1. Platz B + A-1 auf B + 1. Platz nimmt . Es wird kleiner sein. In ähnlicher Weise haben diese Personen auch ein Produkt, das kleiner als $ A \ mal B $ ist, wenn die ersten bis A-1-Personen beim zweiten Mal jeweils die Plätze B + A-1 bis B + 1 einnehmen. Daher ist ersichtlich, dass die zu suchende Lösung 2A-2 oder mehr ist ** ( schränken Sie den zu durchsuchenden Bereich so weit wie möglich ein !! **). Von hier aus sollten Sie überlegen, ** wie viele der ersten A + 1 ~ B- und zweiten A ~ B-1-Personen weniger als AB ** erzielen. Erstens, wenn A = B, gibt es keine solche Person, und wenn A = B-1 ist, ist das erste Mal A + 1 und das zweite Mal ist B-1, so dass die Punktzahl AB + (BA) + 1> ist Da es sich um AB handelt, ist die Punktzahl nicht niedriger als AB (schließen Sie diese beiden fest aus **). Aus dem Obigen werden wir unter B> A + 1 betrachten. Nehmen wir hier an, dass die Person, die sich zum ersten Mal in der Position A + 1 ~ A + x befindet, zum zweiten Mal die Position A + x-1 ~ A einnimmt. Der Maximalwert des Produkts beträgt zu diesem Zeitpunkt $ (2A + x) // 2 \ mal ((2A + x) - (2A + x) // 2) $ (✳︎1). Daher ist für $ 1 \ leqq x \ leqq BA $ $ (2A + x) // 2 \ mal ((2A + x) - (2A + x) // 2) $ kleiner als AB ** Maximum x Sie können ** finden, und ein solches x kann durch ** Dichotomie ** gefunden werden. Achten Sie von oben auf A <= B für die Antwort, die Sie suchen. 2A-2, wenn A = B oder A = B-1 Wenn A <B-1, 2A-2 + x (1 <= x <= B-A) (✳︎2)

(✳︎1)… $ x \ mal y $ (x + y = k) (x, y, k sind alle positive ganze Zahlen) nimmt den Maximalwert (x, y) = (k // 2, kk) an Es wird zum Zeitpunkt von // 2) sein. Dies ist klar, wenn Sie x oder y eliminieren und das Maximum und Minimum oder die Symmetrie von x und y berücksichtigen.

(✳︎2)… Wenn x 1 von B> A + 1 ist, ist das erste Mal A + 1 und das zweite Mal A, also gilt A (A + 1) <AB für die Punktzahl. Daher kann gesagt werden, dass x> = 1 ist.

(✳︎3)… Wenn "jeder" oben geschrieben ist, bedeutet dies, in umgekehrter Reihenfolge zu kombinieren. Zu diesem Zeitpunkt steht auch geschrieben, dass es kleiner als AB sein wird, aber bitte berechnen und überprüfen Sie selbst, ob es kleiner als AB ist. Wenn Sie vor und nach der Kombination suchen, die zu ** AB wird, können Sie auch eine Kombination finden, die kleiner als die letzte Minute ** ist. (Ich konnte es während Bachacon nicht tun, aber als ich mir die Artikel anderer Leute ansah, hielt ich es für eine natürliche Idee.)

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)