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

** A, B, C Probleme ** des ** AtCoder Beginner Contest 182 ** werden mit ** Python3 ** 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, wenden Sie sich bitte an ** Kommentare ** oder ** Twitter **! Twitter: u2dayo

Inhaltsverzeichnis

[ABC182 Zusammenfassung](# abc182-Zusammenfassung) [Ein Problem "twiblr"](# ein Problem twiblr) [B Problem "Fast GCD"](#b Problem fast-gcd) [C Problem "To 3"](#c Problem to-3)

ABC182 Zusammenfassung

Gesamtzahl der Einreichungen: 7497

Performance

Performance AC Ergebnis Zeit Rangfolge(Innerhalb bewertet)
200 AB---- 300 37 Minuten 5814(5649)Rang
400 ABC--- 600 96 Minuten 4832(4668)Rang
600 ABC--- 600 44 Minuten 3991(3829)Rang
800 ABCD-- 1000 100 Minuten 3118(2956)Rang
1000 ABCD-- 1000 50 Minuten 2306(2144)Rang
1200 ABCDE- 1500 96 Minuten 1631(1475)Rang
1400 ABCDE- 1500 67 Minuten 1117(965)Rang
1600 ABCDE- 1500 50 Minuten 744(596)Rang
1800 ABCDE- 1500 37 Minuten 483(341)Rang
2000 ABCDE- 1500 27 Minuten 304(181)Rang
2200 ABCDEF 2100 97 Minuten 185(88)Rang
2400 ABCDEF 2100 80 Minuten 110(40)Rang

Richtige Antwortrate nach Farbe

Farbe Anzahl der Personen A B C D E F
Asche 3040 99.1 % 69.9 % 42.3 % 12.5 % 2.9 % 0.0 %
Tee 1461 99.5 % 97.7 % 87.7 % 51.8 % 12.7 % 0.1 %
Grün 1122 99.5 % 99.5 % 97.2 % 87.5 % 50.7 % 0.6 %
Wasser 692 100.0 % 100.0 % 98.8 % 97.7 % 86.6 % 3.6 %
Blau 357 100.0 % 100.0 % 99.2 % 98.9 % 97.2 % 24.4 %
Gelb 134 96.3 % 96.3 % 95.5 % 96.3 % 91.8 % 59.7 %
Orange 27 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 77.8 %
rot 7 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 100.0 %

Kurzer Kommentar

Ein Problem (7436 Personen AC) "twiblr"
Arithmetik.
B-Problem (6249 AC) "Fast GCD"
$ A_i $ kann bis zu $ 1000 $ betragen. $ 1000 $ ist niemals durch Zahlen größer als $ 1001 $ teilbar. Sie können tatsächlich versuchen, wie viele $ 2 $ bis $ 1000 $ teilbar sind, und die maximale Anzahl ausgeben.
C-Problem (5077 Personen AC) "To 3"
$ N $ ist kleiner als $ 10 ^ {18} $. Das heißt, es gibt nur bis zu 18 $ Ziffern. Es gibt $ 2 $ Möglichkeiten, Ziffern zu löschen, bis zu $ 18 $ für jede Ziffer, mit oder ohne Löschen. $ 2 ^ {18} $ Straßen sind ungefähr $ 26 $ 10.000 Straßen. Sie können also versuchen, alle Ziffern zu löschen und festzustellen, ob es sich um ein Vielfaches von 3 handelt. Dies ist der sogenannte ** Bit Full Search ** -Algorithmus. Beachten Sie, dass Sie nicht alles auf $ 0 $ löschen dürfen. In diesem Fall drucken Sie $ -1 $.
D Problem (3419 Personen AC) "Wandern" [in diesem Artikel nicht erklärt]
Verwenden Sie die kumulative Summe. Sie können es verstehen, indem Sie es auf Papier schreiben.
E Problem (1988 AC) "Akari" [in diesem Artikel nicht erklärt]
Es ist zu spät, um den Platz zu überprüfen, den das Licht für alle Glühbirnen bis zu 50 Millionen US-Dollar erreicht. ** "Ich weiß, dass die Zukunft bereits beleuchtet ist" ** Wenn Sie an diesem Punkt anhalten, beträgt der Berechnungsbetrag $ O (HW + N + M) $ und es wird rechtzeitig sein.
F-Problem (233 Personen AC) "Gültige Zahlungen" [in diesem Artikel nicht erläutert]
Es scheint eine dynamische Planungsmethode zu sein.

Ergebnisse von mir (Unidayo) (Referenz)

screenshot.351.png

Ich denke, ich hätte etwas ruhiger über das D-Problem nachdenken sollen.

Ein Problem "twiblr"

** Problemseite **: A --twiblr ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 99,1% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 99,5% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 99,5%

Erwägung

Es ist eine einfache Arithmetik, aber es ist eine Verschwendung, eine Strafe mit Schwung zu bekommen, daher kann es eine gute Idee sein, eine Weile anzuhalten und sie zu überprüfen.

Code

A, B = map(int, input().split())
print(2 * A + 100 - B)

B Problem "Fast GCD"

** Problemseite **: B - Fast GCD ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 69,9% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 97,7% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 99,5%

Erwägung

** Angenommen, Sie haben eine positive ganze Zahl $ K $. $ K $ ist niemals durch Zahlen teilbar, die größer als $ K $ sind. ** Zum Beispiel ist $ 6 $ niemals durch Zahlen größer als $ 7 $ teilbar.

Da der Maximalwert der Zahlenspalte in diesem Problem auf $ 1000 $ festgelegt ist, ist es sicher, dass Zahlen größer als $ 1001 $ nicht durch $ 1 $ teilbar sind.

Sie können alle teilbaren Zahlen von $ 2 $ bis $ 1000 $ ausprobieren, die Kandidaten für die Antwort sind.

Code

N = int(input())
A = list(map(int, input().split()))

ans = 0
current_max = 0

for x in range(2, 1001):
    score = 0  #Es ist eine teilbare Zahl (GCD-Grad)
    for a in A:
        if a % x == 0:
            score += 1
    if score > current_max:
        ans = x
        current_max = score

print(ans)

C Problem "Bis 3"

** Problemseite **: C - To 3 ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 42,3% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 87,7% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 97,2%

Erwägung

Es mag wie ein Problem erscheinen, das mathematische Überlegungen erfordert, aber tatsächlich kann es gelöst werden, ohne ** "Suche nach allen möglichen Möglichkeiten, um Ziffern zu löschen und zu beurteilen" ** zu entwickeln.

Die $ N $ -Einschränkung beträgt weniger als $ 10 ^ {18} $. Es hat maximal 18 $ Ziffern. Für jede Ziffer gibt es $ 2 $ Möglichkeiten zum Löschen oder Nichtlöschen. Daher gibt es bis zu $ 2 ^ {18} $ Möglichkeiten, Ziffern zu löschen. $ 2 ^ {18} = 262.144 $. Sie können sie alle rechtzeitig ausprobieren.

(Die $ 1 $ -Methode zum Löschen aller Ziffern ist nicht zulässig, es handelt sich also tatsächlich um $ 2 ^ {18} -1 = 262.143 $, sie ist jedoch der Einfachheit halber enthalten.)

Implementierung

"Verwenden / Nicht verwenden" ist "Bit-Vollsuche"

Wenn Sie alle $ 2 $ Straßen von "use / not use" wie dieses Problem durchsuchen möchten, verwenden Sie die sogenannte ** "bit full search" ** -Methode.

Ich werde die Details der Bit-Vollsuche weglassen. (Eigentlich möchte ich im Detail schreiben, aber es ist schwierig, jedes Mal im Detail zu schreiben, wenn eine Vollbit-Suche herauskommt, also kann ich es irgendwo zusammenfassen.)

In Python ist die Vollbit-Suche mit dem "Produkt" des "itertools" -Moduls einfacher.

from itertools import product
product((True, False), repeat=l)

Wenn Sie dies schreiben, werden alle Kombinationen generiert, die für jedes Element mit einer Länge von $ l $ entweder mit "True" oder "False" erstellt werden können.

Beurteilungsmethode von Vielfachen von 3

** "Lösche die Zahlen, klebe sie zusammen und konvertiere sie zurück in ganze Zahlen, um festzustellen, ob sie durch $ 3 $ teilbar sind" scheint offensichtlich ärgerlich. ** ** **

Daher kann es einfach implementiert werden, indem ** "eine bestimmte Ganzzahl $ N $ ist ein Vielfaches von $ 3 $" ⇔ "die Summe der Zahlen in jeder Ziffer von $ N $ ist ein Vielfaches von $ 3 $". ** ** **

(Beispiel: $ 18 → 1 + 8 = 9 $, $ 762 → 7 + 6 + 2 = 15 $)

Erstellen Sie insbesondere eine Liste von $ N $, die durch $ 1 $ -Ziffern zerlegt ist. Zum Beispiel wäre $ 1234567 $ "[1,2,3,4,5,6,7]". Wenn Sie eine bestimmte Ziffer verwenden möchten, ohne sie zu löschen, fügen Sie sie zur Summe der Ziffern hinzu. Wenn Sie sie löschen, fügen Sie sie nicht hinzu. Schließlich können Sie feststellen, ob die Summe der Ziffern ein Vielfaches von $ 3 $ ist.

Sie können nicht alles löschen

Wenn Sie alle Ziffern löschen, beträgt die Summe der Ziffern $ 0 $, sodass es immer ein Vielfaches von $ 3 $ ist. Dieses Problem ist jedoch nicht zulässig.

Das Ausschließen ist mühsam. Wenn die Antwort die Standardeinstellung ist, können Sie $ -1 $ ausgeben.

Code

from itertools import product

#Derzeit ist es einfacher zu handhaben, wenn Sie nach Erhalt als Zeichenfolge S eine Liste mit ziffernweisen Zahlen A erstellen.
# N = 6227384 -> A = [6,2,2,7,3,8,4]

S = input()
A = [int(x) for x in S]

l = len(S)  #Die Anzahl der Ziffern in S (da S als Zeichenfolge empfangen wurde, len(S)Kann verwendet werden)
ans = l

for bits in product((True, False), repeat=l):
    digit_sum = 0  #Es ist die Summe der nicht gelöschten Ziffern
    score = 0  #Je kleiner die Zahl, desto kleiner die Zahl, desto besser
    for i, bit in enumerate(bits):
        if bit:
            #Verwenden Sie diese Option, ohne die i-te Ziffer von oben zu löschen
            digit_sum += A[i]
        else:
            #Löschen Sie die i-te Ziffer von oben
            score += 1

    if digit_sum % 3 == 0:
        #Wenn die Löschmethode ein Vielfaches von 3 ist, aktualisieren Sie den Mindestwert.
        ans = min(ans, score)

if ans == l:
    #Es war also kein Vielfaches von 3-Ausgabe 1
    print(-1)
else:
    print(ans)

Recommended Posts