AtCoder ABC164 Dies ist eine Zusammenfassung der Probleme von AtCoderBeginnerContest164, die am 26.04.2020 (So) in der Reihenfolge von Problem A unter Berücksichtigung der Berücksichtigung durchgeführt wurden. Die zweite Hälfte befasst sich mit dem Problem der DEF (nur D wird aus zeitlichen Gründen richtig zusammengefasst). Klicken Sie hier für die erste Hälfte. 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 Bei einer Zeichenfolge $ S
, die nur aus Zahlen von "1" bis "9" besteht. Eine Reihe von Ganzzahlen, die die folgenden Bedingungen erfüllen (i,j)$(1 \leq i \leq j \leq |S|) Finden Sie die Gesamtzahl von. Bedingung: Wenn Sie die Zeichen $ i $ bis $ j $ von $ S $ als $ 10 $ Dezimalzahlen betrachten, ist diese Ganzzahl ein Vielfaches von $ 2019 $.
Zuerst dachte ich, dass die Einschränkung $ (1 \ leq S \ leq 200000) $ ist, also war ich ehrlich TLE. Das Problem bis C wurde schneller als gewöhnlich gelöst, daher habe ich es bequem interpretiert. Ich stieg aus TLE aus, las das Problem erneut und war enttäuscht.
(1 \leq |S| \leq 200000)
Ich kann es nicht rechtzeitig schaffen ... Danach habe ich mir E- und F-Probleme angesehen und beschlossen, die verbleibenden 90 Minuten für dieses Problem zu verwenden, aber ich konnte es nicht lösen. Wenn Sie nach Abschluss auf Twitter schauen, scheint es sich um ein ähnliches Thema des [ABC158 E-Problems] zu handeln (https://atcoder.jp/contests/abc158/tasks/abc158_e). Schließlich war ich mir sehr bewusst, dass Wachstum nicht zu erwarten ist, ohne Probleme zu lösen, die nicht fest gelöst werden konnten (normale Menschen haben keine andere Wahl, als frühere Fragen zu stellen und ähnliche Probleme lösen zu können, oder?). Ich habe versucht, die Erklärungen zu lesen und einen Artikel zusammenzustellen, indem ich mir frühere Probleme angesehen habe, aber am 28. April sagte @ Seika139: "[ABC164 D-Problem, das auch mit wenigen Zahlen verstanden werden kann (Überschussberechnung)](https: // Ich habe einen Artikel mit dem Titel "qiita.com/Seika139/items/8cacdb3cc8fa6655573c)" gepostet und sanft gelöscht, was ich geschrieben habe. Wenn es einen so zusammenhängenden Artikel gibt, kann ich ihn nicht mehr schreiben (Schweiß) Ich habe auch aus diesem Artikel als Referenz gelernt. Vorläufig habe ich den Code unter Bezugnahme auf den in "ABC164 D-Problem, das auch mit wenigen Zahlen verstanden werden kann (Überschussberechnung)" veröffentlichten Code eingereicht.
abc164d.py
S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1
for s in S:
current = (current + x * int(s)) % 2019
ans += mods[current % 2019]
mods[current % 2019] += 1
x = x * 10 % 2019
print(ans)
Persönlich wusste ich nicht, dass die Kombination mit "ans + = mods [current% 2019]" berechnet werden kann, also habe ich es gelernt. Grundsätzlich ist es notwendig, die Anzahl der Kombinationen zu zählen, bei denen $ D [j] = D [i] $ im Artikel beschrieben ist, aber ich werde berechnen, nachdem $ n $ entschieden wurde. Ich wusste nur, wie es geht.
{}_{m+1} C _2 = {}_m C _2 + m
Daher kann es durch Hinzufügen von $ m $ ... berechnet werden. Ich schämte mich zu sagen, dass ich es nicht wusste. Jetzt müssen Sie nach Abschluss der Berechnung nicht mehr $ {} _n C _2 $ berechnen.
Ich hatte das Gefühl, dass ich es nicht in dem Artikel geschrieben habe, auf den ich mich bezog, also würde ich es gerne ein wenig schreiben, aber es geht um den Grund, warum mods [0] = 1.
Dies ist ungefähr, wenn $ D [i] = 0 $ ist.
In dem Beispiel, auf das in dem Artikel verwiesen wird, wird $ D [i] = 0 $ nicht angezeigt, daher möchte ich das D-Problem mit zwei Beispielen beenden.
Eingabebeispiel 1 ist, wenn $ S = 18171 $. Zu diesem Zeitpunkt beginnt $ D [i] $ bei $ i = 0 $.
Eingabebeispiel 2 ist für $ S = 1817118171 $. Zu diesem Zeitpunkt beginnt $ D [i] $ bei $ i = 0 $.
Nur $ D [i] = 0 $ ist etwas Besonderes, auch wenn Sie nicht an zwei Stellen $ D [i] = 0 $ und $ D [j] = 0 $ auswählen, sondern nur $ D [i] = 0 $ Die Zahlen sind unterschiedlich, weil sie teilbar sind. In dem Artikel, auf den ich mich bezog,
Unter der Annahme, dass das tatsächliche Array $ D $ $ N + 1 $ statt $ N $ lang ist, bereiten Sie einen leeren Raum mit $ D [N + 1] = 0 $ vor. Dies hat mit der Tatsache zu tun, dass es $ {} _ {N + 1} C_2 $ Möglichkeiten gibt, die Indizes $ i, j $ auszuwählen, die den String $ S $ in Scheiben schneiden.
Da es geschrieben wurde, denke ich, dass es hier entspricht, aber durch Hinzufügen des Teils, der nicht $ D [N + 1] = 0 $ hat, $ D [N + 1] = 0 $ und $ D [i Die Auswahl einer Kombination von] = 0 $ entspricht der Auswahl von nur $ D [i] = 0 $.
Dies macht es möglich zu berechnen, also setzen wir mods [0] = 1, um anzunehmen, dass am Anfang $ D [N + 1] = 0 $ steht.
Im eigentlichen Wettbewerb fühle ich mich nicht so verrückt nach Implementierung ...
Problemstellung Es gibt $ N $ Städte, die von $ 1 $ bis $ N $ nummeriert sind. Diese Städte sind durch $ M $ Eisenbahnlinien verbunden. Sie sind derzeit in der Stadt $ 1 $ mit $ 10 ^ {100} $ Goldmünzen und $ S $ Silbermünzen. Die $ i $ -te Bahnlinie verbindet die Stadt $ U_i $ und die Stadt $ V_i $ in beide Richtungen, der einfache Fahrpreis beträgt $ A_i $ Silbermünzen und die Fahrt dauert $ B_i $ Minuten. Der Fahrpreis kann nicht in Goldmünzen bezahlt werden. Jede Stadt hat ein Wechselbüro, in dem Sie 1 $ Goldmünzen gegen $ C_i $ Silbermünzen im $ i $ Wechselbüro eintauschen können. Der Umtausch kostet $ D_i $ pro $ 1 $ Goldmünze. Sie können bei jedem Umtausch so viele Goldmünzen umtauschen, wie Sie möchten. Finden Sie für $ t = 2, ..., N $ die Mindestzeit, die benötigt wird, um von Stadt $ 1 $ zu Stadt $ t $ zu wechseln. Sie können die Wartezeit auf den Zug ignorieren.
Es schien ein Problem bei der Anwendung der Dijkstra-Methode zu sein, aber ich bin nicht einmal an die einfache Implementierung der Dijkstra-Methode gewöhnt, daher denke ich, dass ich diesen Bereich von Grund auf neu studieren muss. Unter den eingereichten Codes bezog ich mich auf Code von Kiri8128, der zum ersten Mal mit Python AC-bestanden wurde. @ kiri8128
abc164e.py
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, S = map(int, input().split())
k = 2451
X = [[] for _ in range(N * k)]
for _ in range(M):
u, v, a, b = map(int, input().split())
u, v = u-1, v-1
for i in range(a, k):
X[u * k + i].append([v * k + i - a, b])
X[v * k + i].append([u * k + i - a, b])
for i in range(N):
c, d = map(int, input().split())
for j in range(k - 1):
X[i * k + j].append([i * k + min(j + c, k - 1), d])
def dijkstra(n, E, i0=0):
h = [[0, i0]]
D = [-1] * n
done = [0] * n
D[i0] = 0
while h:
d, i = hpop(h)
done[i] = 1
for j, w in E[i]:
nd = d + w
if D[j] < 0 or D[j] > nd:
if done[j] == 0:
hpush(h, [nd, j])
D[j] = nd
return D
D = dijkstra(N * k, X, min(S, k - 1))
print(*[min(D[i * k:(i+1) * k]) for i in range(N)][1:], sep = "\n")
Mir fehlt immer noch das Studium, also hoffe ich, dass ich hier langsam lernen kann.
Problemstellung Gegeben ein Array $ S, T, U, V $ der ganzen Zahl $ N $ und der Länge $ N $. Erstellen Sie eine $ 1 $ -Matrix von $ N × N $, die die folgenden Bedingungen erfüllt. ・ $ A_ {i, j} $ ist eine ganze Zahl. ・ $ 0 \ leq a_ {i, j} \ leq 2 ^ {64} $ ・ Wenn $ S_i = 0 $ ist, ist das logische Produkt der Elemente in der Zeile $ i $ $ U_i $. ・ Wenn $ S_i = 1 $ ist, ist das logische Produkt der Elemente in der Zeile $ i $ $ U_i $. ・ Wenn $ S_i = 0 $ ist, ist das logische Produkt jedes Elements in der Spalte $ i $ $ V_i $. ・ Wenn $ S_i = 1 $ ist, ist das logische Produkt jedes Elements in der Spalte $ i $ $ V_i $. Es kann jedoch Fälle geben, in denen keine Matrix vorhanden ist, die die Bedingungen erfüllt.
Derzeit ist weder D noch E gelöst, daher werde ich es eines Tages erneut versuchen (Schweiß) Zunächst muss ich mich stetig von dem Ort entfernen, an dem es gelöst zu sein scheint.
Es scheint, dass es nicht möglich ist, E und F jedes Mal richtig zu organisieren. Ich hoffe, ich kann von vorne anfangen, wenn ich Zeit habe. Vielen Dank, dass Sie die zweite Hälfte bis zum Ende gelesen haben.
Recommended Posts