AtCoder ABC165 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 165, der am 2020-05-02 (Sa) in der Reihenfolge von Problem A unter Berücksichtigung der Berücksichtigung stattfand. Das erste Halbjahr befasst sich mit Fragen bis zu ABCD. Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar PDF
Problemstellung Jumbo Takahashi beschloss, Golf zu üben. Jumbo Takahashis Ziel ist es, die Flugentfernung auf ein Vielfaches von $ K $ zu bringen, aber Jumbo Takahashis Reichweite der Flugentfernung beträgt $ A $ oder mehr und $ B $ oder weniger. Geben Sie "OK" aus, wenn das Ziel erreicht werden kann, und "NG", wenn nicht.
Als ich das Problem auf einen Blick las, war es ein Problem, mehr als ein Vielfaches von $ K $ zu überspringen, und als ich überlegte, eine Ungleichung zu verwenden, fragte ich mich, ob ich die Flugentfernung zu einem Vielfachen von $ K $ machen könnte. Derzeit ist die Einschränkung auch $ 1 \ leq A \ leq B \ leq 1000 $, daher habe ich sie mit der for-Anweisung implementiert. Unten ist der Code, den ich eingereicht habe.
abc165a.py
k = int(input())
a, b = map(int, input().split())
flag = 0
for i in range(a, b + 1):
if i % k == 0:
flag = 1
break
if flag == 1:
print("OK")
else:
print("NG")
Wenn das Spektrum der Einschränkungen jedoch sehr groß ist, ist es nicht rechtzeitig, mit der for-Anweisung zu suchen. Lesen Sie daher den Kommentarartikel.
So finden Sie ein Vielfaches des Maximums von $ K $ unter $ B $ und prüfen, ob es über $ A $ liegt
Ich habe auch versucht zu implementieren, wie man es nach dem Abschluss löst. Unten finden Sie den neu implementierten Code.
abc165a.py
k = int(input())
a, b = map(int, input().split())
x = b // k * k
if a <= x:
print("OK")
else:
print("NG")
Um ehrlich zu sein, konkurriere ich um die Geschwindigkeit, mit der das D-Problem gelöst werden kann. Daher versuche ich vorerst, das A-Problem mit der Methode zu lösen, die ich mir während des Wettbewerbs ausgedacht habe. Da der Python-Operator "//" eine Ganzzahl ausgeben kann, die nach dem Teilungsergebnis abgeschnitten wird, ist x ein Vielfaches des Maximums k, das durch die Berechnung von "x = b // k * k" kleiner oder gleich b ist. Es wird.
Problemstellung Takahashi hat 100 $ Yen bei der AtCoder Bank eingezahlt. Die AtCoder Bank verdient jedes Jahr 1% der Einlagen (doppelte Zinsen, auf die nächste ganze Zahl abgerundet). Unter der Annahme, dass sich der Einzahlungsbetrag nicht aufgrund anderer Faktoren als Zinsen ändert, wie viele Jahre wird es dauern, bis der Einzahlungsbetrag von Takahashi-kun zum ersten Mal $ X $ Yen überschreitet?
Als ich sah, dass die $ X $ -Einschränkung bis zu $ 10 ^ {18} $ betrug, war ich zunächst ziemlich ungeduldig und versuchte, über einige Ideen nachzudenken, aber wenn ich sorgfältig darüber nachdenke, selbst wenn es $ 10 ^ {18} $ ist, innerhalb von $ 10000 $ Jahren, Ich hatte das Gefühl, ich könnte es erreichen, implementieren und 3760 bestätigen. Ich dachte, ich könnte es mir leisten, und als ich versuchte, das Beispiel vor dem Absenden zu überprüfen, war die Eingabe in Beispiel 2 $ 10 ^ {18} $. Wenn Sie es sich zuerst ansehen, konnten Sie möglicherweise die Zeit verkürzen, um es ein wenig zu lösen. Unten ist der implementierte Code.
abc165b.py
x = int(input())
y = 100
for i in range(1, 10000):
y = int(y * 1.01)
if y >= x:
print(i)
break
Problemstellung Angesichts der positiven ganzen Zahlen $ N, M, Q $ und des $ 4 $ Paares von ganzen Zahlen $ (a_i, b_i, c_i, d_i) Q $. Betrachten Sie eine Sequenz $ A $, die die folgenden Bedingungen erfüllt. ・ $ A $ ist eine Folge positiver Ganzzahlen der Länge $ N $. ・ $ 1 \ leq A_1 \ leq A_2 \ leq ⋯ \ leq A_N \ leq M $ Die Punktzahl dieser Zahlenfolge wird wie folgt bestimmt. ・ Summe von $ d_i $ für i, die $ A_ {b_i} −A_ {a_i} = c_i $ erfüllt ($ 0 $, wenn ein solches $ i $ nicht existiert) Finden Sie die maximale Punktzahl für $ A $.
Zum Zeitpunkt des Wettbewerbs konnte ich es mir nicht leisten, $ O (?) $ Zu berechnen. Ich möchte das Problem etwas genauer lösen und ein Gefühl dafür bekommen, ob ich die Suche abschließen kann oder nicht. Als ich über eine Methode zur Lösung nachdachte, hatte ich keine Zeit mehr, also wechselte ich mit "TLE" -Vorbereitung zur vollständigen Suche und implementierte sie. Dies ist vorerst der Code, den ich implementiert und eingereicht habe.
abc165c.py
n, m, q = map(int, input().split())
dict_list = {}
key_list = []
for i in range(0, q):
a, b, c, d = map(int, input().split())
key = tuple([a, b, c])
key_list.append(key)
dict_list[key] = d
def func(i, k, a_list):
if k == 0:
temp_score = 0
for key in key_list:
if key[2] == a_list[key[1]-1] - a_list[key[0]-1]:
temp_score += dict_list[key]
return temp_score
k = k - 1
max_score = 0
for j in range(i, m + 1):
max_score = max(func(j, k, a_list + [j]), max_score)
return max_score
score = 0
for i in range(1, m + 1):
score = max(func(i, n - 1, [i]), score)
print(score)
Für die Zahlenfolge $ A $ in aufsteigender Reihenfolge werden alle Muster mit einer rekursiven Funktion erstellt und die maximale Punktzahl zurückgegeben. Dieses Mal möchte ich, anstatt es zu implementieren, einen kleinen Teil schreiben, in dem es $ {} _ {N + M - 1} C _N $ als Zahlenfolge gibt, die die Bedingungen erfüllt. Diese Art von Problem ist ein Problem, bei dem die Mathematik der High School immer in der Problemsammlung aufgeführt ist und die High School 1 anfängt zu kämpfen. Es sieht nach einem Problem aus, Zahlen in einer Reihe anzuordnen, daher möchte ich $ P $ verwenden, aber es ist ein Problem, dass ich $ C $ verwenden kann, um die Anzahl der Straßen zu ermitteln (ich denke, es ist oft in Scheinprüfungen aufgetaucht).
Die Idee unterscheidet sich ein wenig von der offiziellen Erklärung, aber meine Interpretation besteht darin, an $ N $ Bälle und $ M-1 $ Partitionen zu denken und sie dann in einer Reihe anzuordnen. Dies kann erreicht werden, indem die Anzahl der Bälle und Teiler summiert und nach $ (N + M -1)! $ Angeordnet wird. Aufgrund der Duplizierung jedoch $ N! $ Und $ (M-1)! $ Muss geteilt werden durch (häufige Sequenzprobleme mit doppelten Zeichen). Deshalb,
\frac{(N + M - 1)!}{N!(M - 1)!} = {}_{N+M−1} C _N
Daher können Sie $ C $ verwenden, um die Anzahl der Straßen zu ermitteln. Warum können wir die Anzahl der $ N $ Bälle und $ M-1 $ Teiler in einer Reihe und die Anzahl der $ A $ Zahlen in aufsteigender Reihenfolge finden? Insbesondere $ N = 6, M = Nehmen wir als Beispiel den Fall von 8 $.
Es ist in Ordnung, wenn Sie denken, dass $ A_1, A_2, ..., A_N $ in der Reihenfolge des Kreises links angezeigt werden, also ist Beispiel 1
In Anbetracht des gleichen Beispiels wie in Beispiel 1 sind die Räume 1, 3, 7, 8 leer, und in den Räumen 4, 6 befinden sich zwei, sodass die Zahlenreihe $ A $ lautet
Wenn ich ein Cram-Schullehrer bin, wird mir diese Frage oft von der High School 1 gestellt, daher ist es ziemlich leicht, zu stolpern.
Problemstellung Gegeben sind die ganzen Zahlen $ A, B, N $. Ermitteln Sie den Maximalwert von $ floor (Ax / B) - A × floor (x / B) $ für eine nicht negative Ganzzahl $ x $ kleiner oder gleich $ N $. $ Floor (t) $ repräsentiert jedoch die größte Ganzzahl, die kleiner oder gleich der reellen Zahl $ t $ ist.
Vorerst habe ich ein vollständiges Suchprogramm eingereicht und war "TLE", da ich dachte, ich könnte nicht alle aufzählen (ich denke nicht, dass es eine vollständige Suche geben sollte, die aufgrund des D-Problems einfach zu implementieren ist). Danach habe ich mir die Formel angesehen und die Fälle nach dem, was ich gefunden habe, aufgeteilt und sie ohne Probleme gelöst. Die Reihenfolge der if-Anweisungen im Code wird in der Reihenfolge geschrieben, in der sie während des eigentlichen Wettbewerbs geteilt wurden. Ich erkannte schnell, dass $ floor (Axe / B) $ im weitesten Sinne ein monotoner Anstieg war, also teilte ich die Fälle zuerst durch $ N <B $. Dies ist $ floor (x / B) = 0 $, was leicht zu überlegen ist, daher denke ich, dass es leicht zu finden ist. Da es sich im weitesten Sinne um eine monotone Zunahme handelt, ist ersichtlich, dass $ X = N $ das Maximum ist. Als nächstes wurde durch Einsetzen klar, dass $ N = B $ zu $ Etage (Ax / B) - A × Etage (x / B) = 0 $ wird, also $ X = N-1 $ Sie können sehen, dass es das Maximum ist. Schreiben Sie anschließend durch Ersetzen von $ X = B-1 $ usw. durch Klassifizieren der Fälle nach der Größe von $ A $ und $ B $ den folgenden Code und senden Sie ihn ab: "AC Ich konnte ausstellen.
abc165d.py
a, b, n = map(int, input().split())
max_score = 0
if n < b:
max_score = int(a * n / b) - a * (n // b)
elif n == b:
max_score = int(a * (n-1) / b) - a * ((n-1) // b)
elif a <= b:
max_score = a - 1
elif a >= b:
max_score = int(a * (b-1) / b) - a * ((b-1) // b)
print(max_score)
Als ich mir die Erklärung ansah, kam ich zu einem sehr einfachen Ergebnis, und ich hatte das Gefühl, dass mir die Fähigkeiten fehlten. Als ich die Schlussfolgerung der Erklärung implementierte, konnte ich sie mit dem folgenden Code schreiben (überwiegend kurz).
abc165d.py
a, b, n = map(int, input().split())
x = min(b - 1, n)
print(int(a * x / b) - a * (x // b))
Dies ist das Ende der ersten Hälfte.
Nachdem ich das ABD-Problem gelöst hatte, wurde mir bei diesem Wettbewerb nicht klar, dass es sich bei dem C-Problem um ein vollständiges Suchproblem handelt, und ich habe zu viel Zeit damit verbracht, es zu lösen. Daher hatte ich keine Zeit, es für die E- und F-Probleme zu verwenden, und begann mit dem D-Problem. Ich möchte es in etwa 40 Minuten lösen können. Vielen Dank, dass Sie vorerst bis zum Ende der ersten Hälfte gelesen haben.
In der zweiten Hälfte wird das EF-Problem erläutert. Geplant, um in der zweiten Hälfte fortzufahren.
Recommended Posts