[Erklärung zum AtCoder] Kontrollieren Sie die A-, B-, C- und D-Probleme von ABC181 mit Python!

** A-, B-, C-, D-Probleme ** des ** AtCoder-Anfängerwettbewerbs 181 ** werden mit ** Python 3 ** so sorgfältig wie möglich erklärt.

Ich möchte eine Lösung erklären, die die folgenden drei Punkte erfüllt, nicht nur eine Methode, die gelöst werden kann.

Wenn Sie Fragen oder Anregungen haben, hinterlassen Sie bitte einen Kommentar oder Twitter. Twitter: u2dayo

Inhaltsverzeichnis

[ABC181 Zusammenfassung](# abc181-Zusammenfassung) [Ein Problem "Starke Rotation"](# ein Problem starke Rotation) [B Problem "Trapezsumme"](#b Problem Trapezsumme) [C Problem "Kollinearität"](#c Problem Kollinearität) [D Problem "Hachi"](#d Problem Hachi)

ABC181 Zusammenfassung

Gesamtzahl der Einreichungen: 6643

Performance

Performance AC Ergebnis ()
200 AB---- 300 5056(4953)
400 ABC--- 600 4179(4077)Innerhalb der Rangliste bewertet 20. und 77 ..
600 ABC--- 600 28 Minuten 3435(3333)Rang
800 ABCD-- 1000 95 Minuten 2647(2549)Rang
1000 ABCD-- 1000 60 Minuten 1918(1822)Rang
1200 ABC-E- 1100 87 Minuten 1324(1230)Rang
1400 ABCDE- 1500 83 Minuten 873(789)Rang
1600 ABCDE- 1500 61 Minuten 558(476)Rang
1800 ABCDE- 1500 44 Minuten 345(269)Rang
2000 ABCDEF 2100 103 Minuten 197(139)Rang
2200 ABCDEF 2100 72 Minuten 104(66)Rang
2400 ABCDEF 2100 56 Minuten 52(30)Rang

Richtige Antwortrate nach Farbe

Farbe Anzahl der Personen A B C D E F
Asche 2714 99.0 % 84.1 % 43.0 % 18.0 % 1.4 % 0.1 %
Tee 1228 99.8 % 99.7 % 85.8 % 61.5 % 4.2 % 0.1 %
Grün 972 99.7 % 99.7 % 96.2 % 87.7 % 37.4 % 0.4 %
Wasser 574 99.8 % 99.8 % 98.6 % 95.1 % 86.6 % 7.0 %
Blau 291 99.7 % 99.7 % 100.0 % 98.6 % 98.3 % 38.5 %
Gelb 78 97.4 % 97.4 % 98.7 % 98.7 % 88.5 % 55.1 %
Orange 22 95.5 % 95.5 % 100.0 % 100.0 % 95.5 % 81.8 %
rot 3 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 100.0 %

Kurzer Kommentar

Ein Problem (6568 Personen AC) "Starke Rotation"
Die Antwort hängt davon ab, ob die Anzahl der Tage gerade oder ungerade ist.
B-Problem (5936 Personen AC) "Trapezsumme"
Die Methode, $ A $ auf einfache Weise zu $ B $ hinzuzufügen, ist nicht rechtzeitig. Die Summe jedes Bereichs kann unter Verwendung einer mathematischen Formel unter Verwendung der Tatsache berechnet werden, dass es sich um eine Gleichheitssequenz handelt.
C-Problem (4329 Personen AC) "Kollinearität"
$ 3 $ Beurteilen Sie alle Punktkombinationen in einer schweren Schleife. Die Formel für das Urteil lautet Mathematik an der High School. Ich habe gegoogelt.
D Problem (3152 AC) "Hachi"
"Eine bestimmte Ganzzahl ist ein Vielfaches von 8" ⇔ "Die letzten 3 Ziffern einer bestimmten Ganzzahl sind ein Vielfaches von 8". Versuchen Sie, alle möglichen dreistelligen Kandidaten zu machen, und wenn Sie einen machen können, ist es in Ordnung.
E Problem (1344 Personen AC) "Transformable Teacher" [in diesem Artikel nicht erklärt]
Korrigieren Sie die Größe des Lehrers und sortieren Sie die Anzahl der den Schülern hinzugefügten Höhen in aufsteigender Reihenfolge. Zu diesem Zeitpunkt ist es am besten, mit der nächsten Person wie $ (1, 2), (3, 4), (5, 6), ... $ zu koppeln. Ermitteln Sie für alle Kandidaten für die Lehrergröße die Anzahl der Lehrer in der Dichotomie. Dies kann gelöst werden, indem die Gesamtsumme der Differenzen zu diesem Zeitpunkt unter Verwendung der kumulierten Summe effizient berechnet wird.
F-Problem (230 Personen AC) "Silver Woods" [in diesem Artikel nicht erklärt]
Erhalten Sie alle "Abstände zwischen einem bestimmten Punkt und der oberen Geraden", "Abstände zwischen einem bestimmten Punkt und der unteren Geraden" und "Abstände zwischen zwei Punkten" im Voraus. Verwenden Sie UnionFind, um die Komponenten in aufsteigender Reihenfolge der Entfernung zu verketten. Die Antwort ist der Abstand, wenn die obere und untere gerade Linie dieselbe Verbindungskomponente haben.

Ergebnisse von mir (Unidayo) (Referenz)

screenshot.308.png

Die C- und D-Probleme wurden gegoogelt. Es war ein wenig schwierig, weil ich das E-Problem nicht gut umsetzen konnte, aber insgesamt war es ein faires Ergebnis.

Ein Problem "Starke Rotation"

** Problemseite **: A - Schwere Rotation ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 99,0% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 99,8% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 99,7%

Erwägung

Wenn $ N $ ungerade ist, ist es "Schwarz", und wenn es gerade ist, ist es "Weiß". Wenn der Rest von $ N $ geteilt durch $ 2 $ $ 0 $ ist, ist es eine gerade Zahl, und wenn es $ 1 $ ist, ist es eine ungerade Zahl.

Code

N = int(input())

if N % 2 == 1:
    print("Black")
else:
    print("White")

Problem B "Trapezsumme"

** Problemseite **: B - Trapezsumme ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 84,1% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 99,7% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 99,7%

Erwägung

Wie im folgenden Code gezeigt, ist die Methode zum Hinzufügen von Ganzzahlen von $ A $ zu $ B $ TLE.

N = int(input())

ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    for x in range(a, b + 1):
        ans += x

print(ans)

Um es rechtzeitig zu schaffen, ist es notwendig, die Summe jedes Bereichs mit einer einzigen Formel zu berechnen.

Es gibt ungefähr $ 2 $ in Formeln, aber beide sind ähnlich.

  • $ (Summe der ganzen Zahlen von 1 bis B) - (Summe der ganzen Zahlen von 1 bis A - 1) Find by $ --Verwenden Sie die Summenformel der Gleichheitssequenz mit dem ersten Term $ A $, der Anzahl der Terme $ B-A + 1 $ und der Toleranz von $ 1 $.

Dieses Mal werde ich das einfache erstere erklären.

So finden Sie die Summe von 1 bis x

$ S = (Summe von 1 bis x) $ wird nach der folgenden Formel berechnet. Dieser Ausdruck ist immer in eine ganze Zahl teilbar.

S = \frac{x{(x+1)}}{2}

Im Code sieht es so aus: Beachten Sie, dass wir // (Ganzzahldivision) verwenden, um nach dem Dezimalpunkt abzuschneiden.

s = x * (x + 1) // 2

** Diese Formel wird sehr oft bei Wettkampfprofis verwendet. Wenn Sie sich nicht daran erinnert haben, ist es immer hilfreich, sich bei dieser Gelegenheit daran zu erinnern. ** ** **

Code

def calc(x):
#Eine Funktion, die die Summe von 1 bis x zurückgibt
    return x * (x + 1) // 2


N = int(input())

ans = 0

for _ in range(N):
    a, b = map(int, input().split())
    ans += (calc(b) - calc(a - 1))

print(ans)

C Problem "Kollinearität"

** Problemseite **: C - Kollinearität ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 43,0% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 85,8% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 96,2%

Erwägung

Da die maximale Anzahl von Punkten $ 10 ^ 2 = 100 $ beträgt, ist es ausreichend zu beurteilen, ob alle drei Punktkombinationen auf derselben geraden Linie liegen oder eine schwere Schleife von $ 3 $ verwenden.

Die Bedingung, dass sich die $ 3 $ -Punkte auf derselben geraden Linie befinden, ist, dass die folgende Gleichung gilt. (Für Details überlassen Sie es Offizieller Kommentar und der Google-Suche.)

(x_2-x_1)(y_3-y_1) = (x_3-x_1)(y_2-y_1)

Code

def judge():
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                x1, y1 = P[i]
                x2, y2 = P[j]
                x3, y3 = P[k]
                fx, fy = x2 - x1, y2 - y1
                sx, sy = x3 - x1, y3 - y1
                if fx * sy == sx * fy:
                    return True
    return False


N = int(input())
P = []

for _ in range(N):
    x, y = map(int, input().split())
    P.append((x, y))

if judge():
    print("Yes")
else:
    print("No")

D Problem "Hachi"

** Problemseite **: D --Hachi ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 18,0% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 61,5% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 87,7%

Erwägung

Wenn S 1 oder 2 Stellen ist

Bei $ 1 $ -Ziffern kann es nicht sortiert werden, sodass Sie einfach beurteilen können, ob es durch $ 8 $ teilbar ist.

Bei $ 2 $ -Ziffern können Sie bestimmen, ob es sich um ein $ 2 $ -Muster handelt, das durch $ 8 $ teilbar ist.

Wenn S 3-stellig oder mehr ist

** "Eine bestimmte Ganzzahl ist ein Vielfaches von 8" ⇔ "Die letzten 3 Ziffern einer bestimmten Ganzzahl sind ein Vielfaches von 8" **. Ich werde die Details an anderer Stelle belassen, da $ 1000 $ ein Vielfaches von $ 8 $ ist.

Das heißt, wenn Sie ** $ S $ frei neu anordnen können, um selbst die letzten $ 3 $ -Ziffern zu einem Vielfachen von $ 8 $ zu machen, können Sie es zu einem Vielfachen von $ 8 $ machen. ** ** **

Es gibt nur über 100 $ Vielfache von 8 $ in der 3 $ Ziffer. Daher kann es gelöst werden, indem ** "bestimmt wird, ob alle $ 3 $ -Ziffern für Vielfache von $ 8 $" ** gemacht werden können.

Beurteilungsmethode

Wenn Sie beispielsweise möchten, dass die letzten 3 Ziffern $ 112 $ sind, können Sie dies tun, wenn $ 1 $ $ 2 $ oder mehr und $ 2 $ $ 1 $ oder mehr in $ S $ ist.

Um diese Entscheidung zu treffen, sollten Sie im Voraus zählen, wie viele $ 1 $ bis $ 9 $ in $ S $ enthalten sind.

Implementierung

Zähler beim Zählen

Beim Zählen ist es einfacher, den "Zähler" im Modul "Sammlungen" zu verwenden.

>>> from collections import Counter
>>> S = "181"
>>> cnt_first = Counter(S)
>>> cnt_first
Counter({'1': 2, '8': 1})  # '1'2 Stücke,'8'Da ist einer

So machen Sie ein Vielfaches von 3 Ziffern 8

for x in range(104,1000,8):
    #wird bearbeitet

Geben Sie das Argument von "range" wie folgt an.

Ausgangspunkt: $ 3 $ Das kleinste Vielfache von $ 8 $ in Ziffern $ 104 $ Endpunkt: $ 1000 $ (weniger als) Schritte: $ + 8 $ pro Stück

Jetzt können Sie $ 104, 112, 120, ..., 984, 992 $ aufzählen.

Code

from collections import Counter


def judge():
    if len(S) == 1:
        if int(S) % 8 == 0:
            return True
    elif len(S) == 2:
        if int(S) % 8 == 0 or int(S[::-1]) % 8 == 0:
            return True
    else:
        for x in range(104, 1000, 8):
            cnt_current = Counter(str(x))
            ok = True
            for key, val in cnt_current.items():
                if val > cnt_original[key]:
                    ok = False
            if ok:
                return True
    return False


S = input()
cnt_original = Counter(S)  #Sie können sehen, wie viele Buchstaben 1 bis 9 in S sind

if judge():
    print("Yes")
else:
    print("No")

Beiseite

Offizieller Kommentar ist intelligenter bei der Verwendung von "Counter". Ich denke, du kannst es so machen.

Wir subtrahieren zwischen "Counter" und sagen, dass wir es schaffen können, wenn es leer wird.

Recommended Posts