** 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
[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)
Gesamtzahl der Einreichungen: 6643
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 |
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 % |
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.
** 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%
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.
N = int(input())
if N % 2 == 1:
print("Black")
else:
print("White")
** 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%
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.
Dieses Mal werde ich das einfache erstere erklären.
$ 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. ** ** **
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)
** 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%
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)
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")
** 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%
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.
** "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.
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.
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
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.
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")
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